Relationship Between Community Structure and Clustering Coefficient
Overlapping community is a phenomenon often observed in numerous real-world networks. Fire-spread (Pattanayak et al. in Swarm Evol Comput. 44: 1–48 (2019) [11 ]) community detection algorithm is an efficient algorithm to detect overlapping community struc
- PDF / 952,012 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 230 Views
Abstract Overlapping community is a phenomenon often observed in numerous real-world networks. Fire-spread (Pattanayak et al. in Swarm Evol Comput. 44: 1–48 (2019) [11]) community detection algorithm is an efficient algorithm to detect overlapping community structures. In this work, the Fire-spread algorithm is modified to establish a relationship between community structure and clustering coefficient. By using different networks and executing the modified Fire-spread algorithm, it is found that the clustering coefficient is highly correlated with community structure. Finally, a simpler community detection algorithm, derived from the fire-spread algorithm, is proposed, where the clustering coefficient is used as a threshold value. To validate the proposed algorithm, it is compared with some state of art community detection algorithms based on the NMI score. Keywords Community · Detection · Complex network · Probabilistic computing · Clustering · NMI score · Fire-spread algorithm
1 Introduction Real-world networks vary in sizes and structures. These networks include both naturally occurring networks and human-made networks. In a network, there are few actors (participants) and the interaction between those actors [1]. The actors are generally represented as nodes of the network and interactions are represented as edges. The edges can be directional or non-directional. A social network such as a friendship network, the edges are non-directional whereas an email network [2] H. S. Pattanayak (B) · H. K. Verma · A. L. Sangal Department of CSE, NIT Jalandhr, Jalandhr, India e-mail: [email protected] H. K. Verma e-mail: [email protected] A. L. Sangal e-mail: [email protected] © Springer Nature Singapore Pte Ltd. 2021 S. S. Dash et al. (eds.), Intelligent Computing and Applications, Advances in Intelligent Systems and Computing 1172, https://doi.org/10.1007/978-981-15-5566-4_18
203
204
H. S. Pattanayak et al.
representing email communication between the actors is necessarily directional. Similarly, edges of a network can either be weighted or unweighted. Edges of a friendship network can be unweighted, whereas edges of a co-purchase network [2] are weighted. Networks include social groups, families, villages [3, 4], World Wide Web (web pages containing similar topics are connected more densely among themselves) [4], biological networks [5]. The real-world networks have been studied extensively by the researchers. These networks exhibit scale-free [6] and community structure [7] properties. Community structure is an organization of nodes where some of the nodes are tightly connected with each other compared to the outside nodes [7, 8]. Community detection techniques are used for the detection of suspicious events in the telecom network, detection of terrorist networks, refactoring of software, lung cancer detection [9]. Community detection is the process of identifying the functional groupings without any other information except for the structural information. In community detection, usually, the Mo
Data Loading...
