Research On Overlapping Community Detection Algorithm Based On An EgoNet In Complex Networks

Community structure is an important feature of complex networks,which has a relatively close connection among intra-community nodes and sparse connection of nodes inter-communities.Detecting community structure in networks plays an important role in understanding the network topology and mining the hidden information at the bottom of networks.Therefore,community detection in a network has triggered worldwide interest during recent years.Only non-overlapping communities are studied by traditional community detection algorithms in which nodes belong to only one community.However,most entities have multiple attributes in real networks,that is,nodes in a network could be affiliated to multiple communities at the same time,which makes it more necessary to study overlapping communities.So far,many algorithms have been proposed based on overlapping community discovery in one-mode networks(there is only one type of node in the network),which mainly have two shortcomings: on the one hand,most of the existing algorithms are used to detect community structure of a network from the macro perspective.When the density of edges in inter-communities is higher than that of edges in intra-communities,this kind of methods does not work efficiently.On the other hand,with the increase of network size,the time consumed by such algorithms tends to increase nonlinearly.In recent years,researchers introduced the micro one-mode network model EgoNet,which firstly solves the problem of complex network community discovery from the micro perspective.EgoNet is composed of the central node Ego,the neighbor nodes called Alter and the edges among these nodes.This model can effectively extract the microscopic features of network nodes,which is difficult to be solved by the traditional algorithms.Much literature has also proved that the community discovery algorithm based on the EgoNet has greatly improved execution efficiency.Given the above advantages of EgoNet,a micro bipartite network model,Bi-EgoNet,is proposed and its basic characteristics are briefly studied in this paper.In this work,we study the community discovery problems using the EgoNet and the Bi-EgoNet in one-mode and bipartite networks.The main contribution of this work is as follows in detail.First,the effectiveness of EgoNet in undirected and powerless networks is studied,and an Overlapping Community Detecting algorithm based on Friend Intimacy aliased as OCDFI is proposed.In the traditional community discovering algorithms based on EgoNet,the burden of the merging community is heavy and the accuracy is poor.In this paper,OCDFI is used to extract the ego-local community with high intimacy from each EgoNet.Extracting only one community from each EgoNet can effectively reduce the burden of community merging.Meanwhile,the Ego-local community which only contains Alters with a high degree of intimacy with Ego enables these Alter and Ego to highly likely belong to the same community.This increases the accuracy of the discovery community to some extent.The OCDFI algorithm is verified in both artificial networks and real networks and compared with other classical algorithms.Our experimental results demonstrate that the algorithm has higher accuracy,and the average accuracy is generally improved by 13.39%.Second,the effectiveness of EgoNet in directed and powerless networks is studied.And an Overlapping Community Detecting algorithm based on Attention Degree(OCDAD)is proposed.If node A points to node B,then node A ‘pays attention' to node B in a directed network.In general,the influence of attention between nodes decreases as the distance increases.The traditional calculating methods of Attention Degree only consider the attention influence of the immediate common neighbor,which reduces the accuracy of attention calculating.In this paper,indirect common neighbor nodes ex-Alter are added to the EgoNet model to construct the ex-EgoNet model.Based on this model,when calculating Alter's attention to Ego,the influence of direct and indirect common neighbors are taken into account.We evaluate OCDAD on real networks with known and unknown community structure.Compared with the classical directed network community discovery algorithms OSLOM and Infomap,OCDAD consumes much less time than OSLOM,and a little bit more than that of Infomap,but it is better than these two algorithms in average accuracy,improving by about 35%.Third,the overlapping community discovery problem of a two-mode network is studied in a micro perspective.And an Overlapping Community Detecting algorithm based on Bi-EgoNet,OCDBEN,is proposed.The bipartite network is a special complex network with two different types of nodes.Compared with traditional algorithms,EgoNet is more accurate and effective in detecting community structures in one-mode networks.However,there is no micro-network model that can be used to detect the community structure of a bipartite network so far.Based on this,this work extends EgoNet and proposes a micro bipartite network model Bi-EgoNet.At the same time,OCDBEN is proposed based on Bi-EgoNet.Experimental results on both synthetic and real networks demonstrate that OCDBEN is better than other algorithms in terms of runtime and accuracy: with the increase of network size,our algorithm is significantly less than the other two algorithms(Cui's method and Wang's method)in runtime,and the average accuracy that is improved by about 15.71%.Finally,an Overlapping Community Detecting algorithm of bipartite network based on a Complete Bipartite Graph,OCDCBG,is proposed.Traditional algorithms based on maximal complete subgraphs(or clusters)have great advantages in discovering the community structure of one-mode networks.The complete bipartite graph is a special because it has similar properties with the complete subgraph which is that every node in the complete bipartite graph belongs to the same community.Accordingly,the overlapping community discovery algorithm based on complete bipartite graph in a two-mode networks is developed based on the combination of the undivided property of the complete bipartite graph and the microscopic characteristic of the Bi-EgoNet.Experimental results of both synthetic and real networks indicate that OCDCBG is better than the two classical algorithms(Cui's method and Wang's method)on the average accuracy that is improved by 21.41%.