The Effects of Centrality Ordering in Label Propagation for Community Detection

Brian Dickinson; Wei Hu

doi:10.4236/sn.2015.44012

Home > Journals > Computer Science & Communications > SN

SN> Vol.4 No.4, October 2015

Share This Article:

The Effects of Centrality Ordering in Label Propagation for Community Detection ()

Abstract Full-Text HTML XML

Download as PDF (Size:1941KB) PP. 103-111

DOI: 10.4236/sn.2015.44012 4,117 Downloads 4,635 Views Citations

Author(s) Leave a comment

Brian Dickinson, Wei Hu

Affiliation(s)

Department of Computer Science, Houghton College, Houghton, USA.

ABSTRACT

In many cases randomness in community detection algorithms has been avoided due to issues with stability. Indeed replacing random ordering with centrality rankings has improved the performance of some techniques such as Label Propagation Algorithms. This study evaluates the effects of such orderings on the Speaker-listener Label Propagation Algorithm or SLPA, a modification of LPA which has already been stabilized through alternate means. This study demonstrates that in cases where stability has been achieved without eliminating randomness, the result of removing random ordering is over fitting and bias. The results of testing seven various measures of centrality in conjunction with SLPA across five social network graphs indicate that while certain measures outperform random orderings on certain graphs, random orderings have the highest overall accuracy. This is particularly true when strict orderings are used in each run. These results indicate that the more evenly distributed solution space which results from complete random ordering is more valuable than the more targeted search that results from centrality orderings.

KEYWORDS

Community Detection, Label Propagation, Centrality, Overlapping Community Detection

Cite this paper

Dickinson, B. and Hu, W. (2015) The Effects of Centrality Ordering in Label Propagation for Community Detection. Social Networking, 4, 103-111. doi: 10.4236/sn.2015.44012.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Xie, J., Szymanski, B.K. and Liu, X. (2011) SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process. Proceedings of Data Mining Technologies for Computational Collective Intelligence Workshop at ICDM, Vancouver, 11 December 2011, 344-349. http://dx.doi.org/10.1109/icdmw.2011.154

[2]	Xie, J., Kelley, S. and Szymanski, B. (2013) Overlapping Community Detection in Networks: The State of the Art and Comparative Study. ACM Computing Surveys, 45, 1-35. http://dx.doi.org/10.1145/2501654.2501657

[3]	Zachary, W.W. (1977) An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 33, 452-473.

[4]	Dickinson, B., Valyou, B. and Hu, W. (2013) A Genetic Algorithm for Identifying Overlapping Communities in Social Networks Using an Optimized Search Space. Social Networking, 2, 193-201. http://dx.doi.org/10.4236/sn.2013.24019

[5]	Lusseau, D., et al. (2003) The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations—Can Geographic Isolation Explain This Unique Trait? Behavioral Ecology and Sociobiology, 54, 396-405. http://dx.doi.org/10.1007/s00265-003-0651-y

[6]	Estrada, E. and Rodriguez-Velazquez, J.A. (2005) Subgraph Centrality in Complex Networks. Physical Review, 71, Article ID: 056103. http://dx.doi.org/10.1103/physreve.71.056103

[7]	Freeman, L.C. (1979) Centrality in Social Networks I: Conceptual Clarification. Social Networks, 1, 215-239. http://dx.doi.org/10.1016/0378-8733(78)90021-7

[8]	Brandes, U. (2001) A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, 25, 163-177. http://dx.doi.org/10.1080/0022250X.2001.9990249

[9]	Valyou, B., Dickinson, B. and Hu, W. (2014) Determining Leaders and Communities on Networks Using Neighborhood Similarity. Social Networking, 3, 50-57. http://dx.doi.org/10.4236/sn.2014.31006

[10]	Bonacich, P. and Paulette, L. (2001) Eigenvector-Like Measures of Centrality for Asymmetric Relations. Social Networks, 23, 191-201. http://dx.doi.org/10.1016/S0378-8733(01)00038-7

[11]	Brin, S. and Page, L. (1998) The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the 7th World-Wide Web Conference, Brisbane, April 1998. http://dx.doi.org/10.1016/s0169-7552(98)00110-x

[12]	Xing, Y. (2014) A Node Influence Based Label Propagation Algorithm for Community Detection in Networks. The Scientific World Journal, 2014, Article ID: 627581. http://dx.doi.org/10.1155/2014/627581

[13]	Newman, M.E.J. (2004) Finding and Evaluating Community Structure in Networks. Physical Review E, 69, Article ID: 026113. http://dx.doi.org/10.1103/physreve.69.026113

[14]	Danon, L., Diaz-Guilera, A., Duch, J. and Arenas, A. (2005) Comparing Community Structure Identification. Journal of Statistical Mechanics: Theory and Experiment, 9, Article ID: P09008. http://dx.doi.org/10.1088/1742-5468/2005/09/p09008

[15]	Shen, H., Cheng, X., Cai, K. and Hu, M.B. (2009) Detect Overlapping and Hierarchical Community Structure in Networks. Physica A, 388, 1706-1712. http://dx.doi.org/10.1016/j.physa.2008.12.021