Internal Structure Of Community In Complex Networks

Real systems in various fields,e.g.,power grids in engineering,gene regulatory networks in biology,and circles of friends in social media like Facebook,are best formulated as graphs or networks where nodes represent entities and links represent relationships between entities.Complex networks are not random,but rather have various structural and locational properties.One important property common to many networks is the presence of com-munity structure,where the nodes within a community are more densely connected than the nodes across two communities.Community structure is an important network property since they typically constitute functional units of a network.For instance,groups in social networks often possess their own norms,orientations and subcultures.Within a cell,some proteins interact to form protein complexes to exert their functions.In this paper,we mainly focus on the community structure,especially the internal structure of community.The first of six chapters is the introduction.We introduce the concept of complex networks and the research directions of complex net-works,especially community structure.The main contents are concluded from the second chapter to the fifth chapter,and the innovation points are included in these chapters.In the sixth chapter,we give a summary about our work firstly,then give several research topic which are hope to be solved in the future.Firstly,we introduce the concepts of leader community and self-organizing community.Also,we explore the important role of the leader nodes in com-munities.However,to the best of our knowledge,there is not much at-tention given to investigating the internal structure of communities in the literature.In the second chapter of this paper,we study community struc-tures of more than twenty real world networks using ten commonly used community-detecting methods,as a result,we discovery that most commu-nities have several leaders whose degrees are particularly large.We use a statistical parameter,variance,to classify the communities as leader com-munities and self-organized communities.In a leader community,we defined the nodes with largest 10%degree as its leaders.In our experiences,when we remove the leaders,on average community's internal edges are reduced by more than 40%and inter-communities edges are reduced by more than 20%.In addition,the community's average clustering coefficient decrease.These facts suggest that the leaders play an important role in keeping communities denser and more clustered,and it is the leaders that are more likely to link to other communities.Moreover,similar results for several random networks are obtained,and a theoretical lower bound of the lost internal edges is giv-en.Our study shed light on the further understanding and studying of the internal community structure in complex networks.Secondly,we propose a new index to identify leader community and self-organizing community,called degree variance ratio p.Leader communities and self-organizing communities have been introduced recently to characterize networks and understand how communities arise in complex networks.How-ever,identification of leader and self-organizing communities is technically challenging since no adequate quantification has been developed to properly separate the two types of communities.We introduced a new measure,called ratio of node degree variances,to distinguish leader communities from self-organizing communities,and developed a statistical model to quantitatively characterize the two types of communities.We experimentally studied the power and robustness of the new method on several real-world networks in combination of some of the existing community identification methods.Our results revealed that social networks and citation networks contain more lead-er communities whereas technological networks such as power grid network have more self-organizing communities.Moreover,our results also indicated that self-organizing communities tend to be smaller than leader communities.The results shed new lights on community formation and module structures in complex systems.Thirdly,we explore the relationship of different communities.Com-munity structure and core-periphery structure are two natural properties of complex networks.Both structures have been studied separately for decades.However,few researchers focus on the combination of these two important structures in complex networks.In this paper,we explore the core-periphery structures of communities in complex networks especially community net-works,more precisely,we propose a linear algorithm to divide each commu-nity into a densely interconnected core and a periphery where the nodes are rarely linked to each other.Based on core-periphery structures,we perform quantitative analysis of the edges between different communities and find two relationships of two communities in real networks:unitive and multi-polar.Communities are called unitive if edges between different cores are more than edges between different peripheries.Otherwise,communities are called multipolar.Furthermore,we propose a random model called General ized Girvan-Newman(GGN)model,which can generate community networks where communities are either unitive or multipolar.The model sheds some new light on community formation and core-periphery structures in complex systems.Lastly,we propose a new algorithm to detect communities in complex networks.Detecting community structures is an important step to under-standing the structure and dynamics of real-world networks in social science,biology and technology.In this paper,based on non-negative matrix factor-ization we develop a deep stochastic model to identify communities,in which there are two sets of parameters.One is the community membership matrix,of which the element in the i-th row and k-th column represents the probabil-ity node i belongs to community k in our model.Another is the community-community connection matrix,of which the element in the i-th row and j-th column represents the probability of there being an edge between a randomly chosen node from the i-th community and a randomly chosen node from the j-th community.The parameters can be evaluated by an efficient updating rule whose convergence can be guaranteed.The community-community con-nection matrix in our model is more precise than the community-community connection matrix in traditional non-negative matrix factorization methods.Furthermore,the method called Symmetric Nonnegative Matrix Factoriza-tion(SNMF),is a special case of our model.