Overlapping Community Detection Algorithms Based On Complex Networks

Complex networks spread all areas of human life and the theory about it has arousedwidespread concern. A remarkable feature of complex networks is the presence ofcommunity structure, community mining has gradually become an emerging research topic.In complex networks with community structure, nodes in networks are often found tocluster into tightly knit groups with a high density of within-group edges and a lowerdensity of between-group edges.This paper introduces the research background, research significance, research statusof community structure detection and had a detailed analysis of the merits, demerits andscope of application of each algorithm. The overlapping community discovery algorithmsapplied in undirected and unweighted network and directed and weighted network havebeen proposed, the main research content is outlined as follows:i. An overlapping community discovery algorithm TROC based on triangle is given,the algorithm is applied only to the undirected and unweighted network. If two adjacentnodes and their shared neighbor nodes can constitute a triangle, the two nodes areconsidered in the same community. The proposed TROC algorithm has been tested on thecomputer-generated and two real networks of Zachary’s karate club network and Dolphin’ssocial network, all identified the community structure and overlapping nodes correctly, theresults showed the algorithm is feasible and effective for detecting overlappingcommunities.ii. In the directed and weighted e-mail network, a variety of features had been studied,such as centrality, small community stability and small world etc. This paper given theinnovative definition of the edge weight, the definition of weight coefficient which is used to judge the close links between the two nodes, at the same time, the importance of theedge evaluation methods is given.iii. For the e-mail network, this paper proposes edge community mining algorithmwhich puts the edge as research object. Firstly, the EdgeSort algorithm is used to give theimportance of edge sorting and choose the seed edge as the initial community and thenextend the community. In the process of the community expansion, this paper put forwardthe concept of edge community fitness and edge fitness. The results of the LELFM isverified on the Enron data set and compared with the LFM algorithm and the improvedweighted GN algorithm, which demonstrated the effectiveness of this algorithm in thedirected and weighed network.