Determining Leaders and Communities on Networks Using Neighborhood Similarity

Benjamin  Valyou; Brian  Dickinson; Wei  Hu

doi:10.4236/sn.2014.31006

Benjamin Valyou, Brian Dickinson, Wei Hu^*

Abstract: Networks are used to represent interactions in a wide variety of fields, like biology, sociology, chemistry, and more. They have a great deal of salient information contained in their structures, which have a variety of applications. One of the important topics of network analysis is finding influential nodes. These nodes are of two kinds —leader nodes and bridge nodes. In this study, we propose an algorithm to find strong leaders in a network based on a revision of neighborhood similarity. This leadership detection is combined with a neighborhood intersection clustering algorithm to produce high quality communities for various networks. We also delve into the structure of a new network, the Houghton College Twitter network, and examine the discovered leaders and their respective followers in more depth than which is frequently attempted for a network of its size. The results of the observations on this and other networks demonstrate that the community partitions found by this algorithm are very similar to those of ground truth communities.

Keywords: Community Detection; Community Leaders; Node Importance; Centrality; Neighborhood Similarity; Modularity

Cite this paper: Valyou, B. , Dickinson, B. and Hu, W. (2014) Determining Leaders and Communities on Networks Using Neighborhood Similarity. Social Networking, 3, 50-57. doi: 10.4236/sn.2014.31006.

References

[1] U. N. Raghavan, R. Albert and S. Kumara, “Near Linear Time Algorithm to Detect Community Structures in Large- Scale Networks,” Physical Review E, Vol. 76, No. 3, 2007, Article ID: 036106. http://dx.doi.org/10.1103/PhysRevE.76.036106

[2] J. Xie, B. K. Szymanski and X. Liu, “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-14 December 2011, pp. 344-349.

[3] J. Xie and B. K. Szymanski, “LabelRank: A Stabalized Label Propagation Algorithm for Community Detection in Networks,” Proceedings of the IEEE Network Science Workshop, West Point, 29 April-1 May 2013, pp. 138- 143.

[4] J. Huang, H. Sun, Y. Liu, Q. Song and T. Weninger, “Towards Online Multiresolution Community Detection in Large-Scale Networks,” PLoS ONE, Vol. 6, No. 8, 2011, p. e23829. http://dx.doi.org/10.1371/journal.pone.0023829

[5] R. Rabbany, J. Chen and O. R. Zaiane, “Top Leaders Community Detection Approach in Information Networks,” Proceedings of the 4th SNA-KDD Workshop on Social Network Mining and Analysis, The ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Washington DC, 2010.

[6] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, Vol. 33, No. 4, 1977, pp. 452-473.

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

[8] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten and S. M. Dawson, ”The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations,” Behavioral Ecology and Sociobiology, Vol. 54, No. 4, 2003, pp. 396-405. http://dx.doi.org/10.1007/s00265-003-0651-y

[9] P. Gleiser and L. Danon, “Community Structure in Jazz,” Advances in Complex Systems, Vol. 6, No. 4, 2003, pp. 565-573. http://dx.doi.org/10.1142/S0219525903001067

[10] M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, No. 12, 2002, pp. 7821-7826. http://dx.doi.org/10.1073/pnas.122653799

[11] J. Leskovec, J. Kleinberg and C. Faloutsos. “Graph Evolution: Densification and Shrinking Diameters,” ACM Transactions on Knowledge Discovery from Data, Vol. 1, No. 1, 2007, Article 2.

[12] X. Liu, Z. Xie and D.-Y. Yi, “Community Detection by Neighborhood Similarity,” Chinese Physics Letters, Vol. 29, No. 4, 2012, Article ID: 048902. http://dx.doi.org/10.1088/0256-307X/29/4/048902

[13] G. Csardi and T. Nepusz, “The Igraph Software Package for Complex Network Research,” InterJournal, Vol. Complex Systems, 2006. http://igraph.sf.net

[14] R Core Team, “R: A Language and Environment for Statistical Computing,” R Foundation for Statistical Computing, Vienna, 2013. http://www.R-project.org/

[15] M. Rosvall and C. T. Bergstrom, “Maps of Information Flow Reveal Community Structure in Complex Networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 105, No. 4, 2008, pp. 1118- 1123. http://dx.doi.org/10.1073/pnas.0706851105

[16] A. Clauset, M. E. J. Newman and C. Moore, “Finding Community Structure in Very Large Networks,” Physical Review E, Vol. 70, No. 6, 2004, Article ID: 066111. http://dx.doi.org/10.1103/PhysRevE.70.066111