1. Lengthening of average path length in social networks due to the effect of community structure
- Author
-
Amrit Lal Sangal, Harsh Kumar Verma, and Himansu Sekhar Pattanayak
- Subjects
Random graph ,General Computer Science ,Social network ,business.industry ,Computer science ,Artificial networks ,Community structure ,020206 networking & telecommunications ,02 engineering and technology ,Graph model ,Average path length ,Fire spread ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,business ,Algorithm - Abstract
Community structure is a common phenomenon observed in various social networks. In this work, a novel community detection algorithm is proposed by estimating the effect of community structure on the average path length of a network. The Erdos-Renyi graph model is used as a reference to compute the change in the average path length of a network due to community formation. By experimenting with artificial networks, it is found that community structure in a social network contributes towards the lengthening of the average shortest path length. A random graph is found to have a lesser average shortest path length than a social network with community structure. As the size of individual communities increases, there is a decrease in the difference of average shortest path lengths, compared with a random graph containing an equal number of nodes and edges. This relationship is used to predict the average community size and their numbers in a network. The findings mentioned above are applied to the proposed algorithm. The proposed community detection algorithm is an enhancement over Fire Spread community detection algorithm (Pattanayak, 2019), in which the value of R for the R-radius neighborhood subgraph is automatically calculated.
- Published
- 2022