Detecting Geographically Dispersed Overlay Communities Using Community Networks

Authors: Madhushi Bandara, Dharshana Kasthurirathna, Danaja Maldeniya, Mahendra Piraveenan

Abstract:

Community detection is an extremely useful technique in understanding the structure and function of a social network. Louvain algorithm, which is based on Newman-Girman modularity optimization technique, is extensively used as a computationally efficient method extract the communities in social networks. It has been suggested that the nodes that are in close geographical proximity have a higher tendency of forming communities. Variants of the Newman-Girman modularity measure such as dist-modularity try to normalize the effect of geographical proximity to extract geographically dispersed communities, at the expense of losing the information about the geographically proximate communities. In this work, we propose a method to extract geographically dispersed communities while preserving the information about the geographically proximate communities, by analyzing the ‘community network’, where the centroids of communities would be considered as network nodes. We suggest that the inter-community link strengths, which are normalized over the community sizes, may be used to identify and extract the ‘overlay communities’. The overlay communities would have relatively higher link strengths, despite being relatively apart in their spatial distribution. We apply this method to the Gowalla online social network, which contains the geographical signatures of its users, and identify the overlay communities within it.

Keywords: Social networks, community detection, modularity optimization, geographically dispersed communities.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1339858

References:

[1] R. Albert and A.-L. Barab´asi, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, pp. 47–97, 2002.
[2] D. Kasthurirathna, A. Dong, M. Piraveenan, and I. Y. Tumer, “The failure tolerance of mechatronic software systems to random and targeted attacks,” in ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2013, pp. V005T06A036–V005T06A036.
[3] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
[4] M. E. Newman, “The structure and function of complex networks,” SIAM review, vol. 45, no. 2, pp. 167–256, 2003.
[5] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Statistical properties of community structure in large social and information networks,” in Proceedings of the 17th international conference on World Wide Web. ACM, 2008, pp. 695–704.
[6] M. E. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006.
[7] P. Shakarian, P. Roos, D. Callahan, and C. Kirk, “Mining for geographically disperse communities in social networks by leveraging distance modularity,” in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013, pp. 1402–1409.
[8] M. G. Herander and L. A. Saavedra, “Exports and the structure of immigrant-based networks: the role of geographic proximity,” Review of Economics and Statistics, vol. 87, no. 2, pp. 323–335, 2005.
[9] R. Medina and G. Hepner, Geospatial analysis of dynamic terrorist networks. Springer, 2008.
[10] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of statistical mechanics: theory and experiment, vol. 2008, no. 10, p. P10008, 2008.
[11] P. Expert, T. S. Evans, V. D. Blondel, and R. Lambiotte, “Uncovering space-independent communities in spatial networks,” Proceedings of the National Academy of Sciences, vol. 108, no. 19, pp. 7663–7668, 2011.
[12] J. Hannigan, G. Hernandez, R. M. Medina, P. Roos, and P. Shakarian, “Mining for spatially-near communities in geo-located social networks,” arXiv preprint arXiv:1309.2900, 2013.
[13] X. Liu, T. Murata, and K. Wakita, “Extracting the multilevel communities based on network structural and nonstructural information,” in Proceedings of the 22nd international conference on World Wide Web companion. International World Wide Web Conferences Steering Committee, 2013, pp. 191–192.
[14] K. Aberer, L. O. Alima, A. Ghodsi, S. Girdzijauskas, S. Haridi, and M. Hauswirth, “The essence of p2p: a reference architecture for overlay networks,” in Peer-to-Peer Computing, 2005. P2P 2005. Fifth IEEE International Conference on. IEEE, 2005, pp. 11–20.
[15] J. Leskovec and A. Krevl, “{SNAP Datasets}:{Stanford} large network dataset collection,” 2014.
[16] R. Albert, H. Jeong, and A.-L. Barab´asi, “Error and attack tolerance of complex networks,” nature, vol. 406, no. 6794, pp. 378–382, 2000.
[17] M. E. J. Newman, “Mixing patterns in networks,” Physical Review E, vol. 67, no. 2, p. 026126, 2003.
[18] Lirneasia. (Online). Available: http://www.lirneasia.net