Research On The Key Technologies Of Community Detection In Complex Networks

Most of the complex systems in real world can be modeled as a complexnetworks. Numerous studies reveal that there generally exist underlying communitystructures in complex networks, which always represent the set of nodes that owningthe same attributes or playing the similar roles. Community detection has importanttheoretical significance and wide application prospects, since it can explore thestructures and functions of networks. Currently, community detection has becomeone of the most important and challengeable research subjects in various domains.We take community detection as the research object and aim to solve four keyproblems. The main research works are listed as follows:1. For non-overlapping community detection problems, we propose asemi-supervesed community detection algorithm based on fast affinity propagation(SCAN-FAP), which is mainly composed of two important parts. The first one is theconstraint SimRank similarities, which are used to integrate the prior knowledge.The seconde one is a proposed method that can use the similarities effectively tohelp improve the community detection quality. Experimental results demonstratethat, SCAN-FAP can not only utilize the prior knowledge effectively and improvethe community detection quality significantly, but also performs better than thestate-of-art semi-supervised clustering algorithms.2. For overlapping community detection problems, we proposed a density-basedlink clustering algorithm (DBLINK), which firstly utlize the density-basedclustering method to partition the edge set of the networks into disjoint linkcommunities, which then will be transformed into the final node communities.DBLINK has the ability of identifying the isolated edges that satisfied with certaincondition and assigning them into no link community. An empirical evaluation ofthe method using both synthetic and real datasets demonstrates demonstrate theefficiency and effectiveness of DBLINK.3. For community detection problems in dynamic networks, we propose anincremental dentisty-based link algorithm for overlapping communities in dynamicnetworks (iDBLINK), which update the local community sturctures by the similaritychanges between edges. iBLINK only pay attentation to the the changes of disjointlink, however, the changes of overlapping node communities will be naturelyreflected by the disjoint link communities updating. An empirical evaluation of the method using both synthetic and real datasets demonstrates demonstrate theefficiency and effectiveness of iDBLINK.4. For local community detection problems, we proposed a local communitydetection algorithm base on maximum clique extension called LCD-MC. Theproposed method firstly finds the set of all the maximum cliques of the source node,and initializes them as the starting local communities; then, it expands eachunclassified local communities by greedy optimization until a certain condition. Anempirical evaluation of the method using both synthetic and real datasetsdemonstrates demonstrate the effectiveness of LCD-MC.