Detecting Overlapping and Hierarchical Communities in Complex Network Based on Maximal Cliques
Community detection is a fundamental task in discovering complex network. Maximal cliques are found to play significant roles in communities. This paper proposes an efficient algorithm OMC for detecting communities based on maximal cliques. Subordinate ma
- PDF / 1,151,932 Bytes
- 8 Pages / 439.37 x 666.14 pts Page_size
- 113 Downloads / 227 Views
)
School of Software Engineering, South China University of Technology, Guangzhou, People’s Republic of China [email protected], [email protected] Abstract. Community detection is a fundamental task in discovering complex network. Maximal cliques are found to play significant roles in communities. This paper proposes an efficient algorithm OMC for detecting communities based on maximal cliques. Subordinate maximal cliques are removed and remaining cliques are regarded as initial communities. Then small communities are merged into larger ones according to a fitness function. The proposed algorithm is able to uncover both overlapping and hierarchical communities in high speed. Exper‐ imental results on various real-word networks have proven that the method performed well in detecting communities. Keywords: Community detection · Maximal cliques · Overlapping · Hierarchical · Fitness function
1
Introduction
Real-word systems are often formed in terms of complex networks or graphs. Examples are biological networks, co-authorship network, protein interaction graphs, social network [1, 2]. Nodes in networks represent entities and links represent relations between entities. Community is found universal existing in complex network. A community might correspond to a certain functional unit in a protein network or a group of students study together in social network. However, there is not a uniform definition of community. Intuitively, community is the structure in complex network that has density links within but less connections to other communities. A great deal of methods or algorithms have been proposed to detect communities in recent years, making it a hot interdisciplinary problem. Traditional algorithms provide a partition of network without overlapping. However, the overlapping information is later found significant in community detection. A node can play various roles in networks and belongs to several communities. For example in social network, a node represents a teacher might be head teacher in a class and also a member of faculty staffs. Palla proposed the first method CPM in which could detect overlapping communities. After Palla’s work, maximal cliques have been widespread concern in community discovery. Significant roles that cliques play in communities have been pointed out in details in this paper. Density parts of complex network tend to form larger cliques. © Springer Science+Business Media Singapore 2015 X. Zhang et al. (Eds.): SMP 2015, CCIS 568, pp. 184–191, 2015. DOI: 10.1007/978-981-10-0080-5_17
Detecting Overlapping and Hierarchical Communities
185
Basic structures of many communities are composed of maximal cliques. Subordi‐ nate cliques are proposed to remove disturbed maximal cliques. The paper proposes an algorithm based on Optimization over Maximal Cliques (OMC), which could detect overlapping community and also give hierarchical structure of communities. The algorithm applies the object function of fitness and evaluation function of extended modularity. Most methods based on optimization us
Data Loading...
