Research On Community Detection Algorithms Based On Community Property

Complex systems exist in various industrial and living environment,where complex networks are often used as the abstraction of these systems.Static complex networks are generally constructed to represent the system information.Accordingly,the networks would be dynamic if the systems evolve temporally and spatially.As the fastdeveloping information technology leads to an insistent demand to mine the potential structural properties for exploring the functions of complex systems,extracting productive information from these complex networks has become a vital task to promote the technological development in relevant domains.Community detection is a such research that aims at static or dynamic networks to detect the modules(i.e.,communities)with dense internal connections inside the modules and sparse external connections among different modules.Since system functions are closely related to their structures,detecting community structure is of great guiding significance to system function analysis.In recent years,community detection has caught much attention from researchers,and detection in large-scale networks and dynamic networks is exactly the current research hotspot.Through a comprehensive literature review,we found that the existing methods of community detection have been studied from different perspectives and achieved fruitful results.However,many of them have obvious drawbacks even with good performance,especially for large-scale networks and dynamic networks.This leaves community detection in need of further research.Based on the intrinsic properties of community,two methods are proposed for detecting communities in static networks,besides this,we also carry out the researches about detecting single community containing the given node using only local information of networks and detecting community structrues in dynamic networks.Specifically,the main contents and contributions of this thesis contain the following three aspects.1.Two community-detection methods for static networks.1)Intrinsic-prop: a community detection method based on community intrinsic properties.This method considers not only the relationship between each node and its 1-hop neighbors,but also the relationship between the node and its 2-hop neighbors.A node’s closely connected neighbor nodes are selected to form the community center.Further,a condition of absorbing community members is defined to expand and merge community centers for obtaining the final community structure.2)NSCLS: a node similarity and community link strength-based community discovery method.In NSCLS,a novel way of calculating node similarities is designed for community initialization.Moreover,a concept of calculating community link strength is proposed,so that we can merge some initial communities to get the final results.In terms of the results of Intrinsic-prop,two adjacency nodes having more common neighbors are generally in the same community,and each node has the same community affiliation with most of its neighbors.Regarding NSCLS’s results,each node belongs to the same community as its most similar neighbor(s).These properties ensure the quality of the detected community structure.Furthermore,the superior performance of both methods on synthetic networks and real-world networks illustrates their effectiveness.2.3L: local community uncovered by local clusters and local modularity.This is a framework of local community detection,which only uses local information of local area in the network to detect the target community that contains the given node.The method first creates the core cluster containing the given node,then builds a series of peripheral clusters surrounding the core,to determine the approximate range of the local community.The relationship between clusters is further considered to obtain the target community.Due to the insensitivity to the beginning node,3L alleviates the problem that the target community cannot be uncovered effectively when the beginning node is at the community boundary.Thus,3L can be applied in large-scale networks or the networks where global information is unavailable.Through the solid experiments,3L acquires high-quality target community.3.Spiderweb: a model for community detection in dynamic networks.This method detects communities from dynamic networks in an incremental way.It firstly extracts the community structure of the first snapshot by Intrinsic-prop,and deals with the events of node or edge additions or remvoals through simulating the spiderweb evolution,to incrementally discover the community structures of the succeeded snapshots.This method not only obtains the high-quality community structure on each snapshot,but also maintains the evolutionary smoothness of community structures between two successive snapshots.Extensive experiments on both synthetical networks and real-world networks show the stability and superiority of Spiderweb over the SOTA baselines.In summary,the proposed methods,namely Intrinsic-prop,NSCLS,3L,and Spiderweb,can detect high-quality communities in static networks and dynamic networks respectively.They provide effective solutions for the problem of community detection in complex networks,and can be utilized to facilitate and promote the study of other network-analysis tasks.