Detecting Geographically Dispersed Overlay Communities Using Community Networks

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.

Authors:

• Madhushi Bandara
• Dharshana Kasthurirathna
• Danaja Maldeniya
• Mahendra Piraveenan

Keywords:

• Social networks
• community detection
• modularity optimization
• geographically dispersed communities.

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