Fast community structure local uncovering by independent vertex-centred process

ABSTRACT

This paper addresses the task of community detection and proposes a local approach based on a distributed list building, where each vertex broadcasts basic information that only depends on its degree and that of its neighbours. A decentralised external process then unveils the community structure. The relevance of the proposed method is experimentally shown on both artificial and real data.

References

1. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, 1st ed. Cambridge: Cambridge University Press, Nov. 1994.
2. A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, "Impact of Human Mobility on Opportunistic Forwarding Algorithms," IEEE Transactions on Mobile Computing, vol. 6, no. 6, pp. 606--620, Jun. 2007.
3. N. Vastardis and K. Yang, "Mobile Social Networks: Architectures, Social Properties, and Key Research Challenges," IEEE Communications Surveys Tutorials, vol. 15, no. 3, pp. 1355--1371, 2013.
4. K. Lee, P. Hui, and S. Chong, "Mobility Models in Opportunistic Networks," in Mobile Ad Hoc Networking, S. Basagni, M. Conti, S. Giordano, and I. Stojmenovic, Eds. John Wiley & Sons, Inc., 2013, pp. 360--418.
5. P. Hui, E. Yoneki, S. Y. Chan, and J. Crowcroft, "Distributed Community Detection in Delay Tolerant Networks," in Proc. of the 2007 ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture, ser. MobiArch '07. New York, NY, USA: ACM, 2007, pp. 7:1--7:8.
6. P. Hui, J. Crowcroft, and E. Yoneki, "BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks," IEEE Transactions on Mobile Computing, vol. 10, no. 11, pp. 1576--1589, Nov. 2011.
7. M. Laibowitz, J. Gips, R. Aylward, A. Pentland, and J. Paradiso, "A sensor network for social dynamics," in Proc. of the 2006 Information Processing in Sensor Networks (ISPN), 2006, pp. 483--491.
8. J. A. Paradiso, J. Gips, M. Laibowitz, S. Sadi, D. Merrill, R. Aylward, P. Maes, and A. Pentland, "Identifying and Facilitating Social Interaction with a Wearable Wireless Sensor Network," Personal Ubiquitous Computing, vol. 14, no. 2, pp. 137--152, 2010.
9. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, "Defining and identifying communities in networks," Proc. of the National Academy of Sciences, vol. 101, no. 9, pp. 2658--2663, Mar. 2004.
10. S. Fortunato, "Community detection in graphs," Physics Reports-Review Section of Physics Letters, pp. 75--174, Jun. 2009.
11. B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, no. 2, pp. 291--307, 1970.
12. C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Communications of the ACM, vol. 16, no. 9, pp. 575--577, Sep. 1973.
13. L. Freeman, "A Set of Measures of Centrality Based on Betweenness," Sociometry, vol. 40, no. 1, pp. 35--41, Mar. 1977.
14. M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proc. of the National Academy of Sciences, vol. 99, no. 12, pp. 7821--7826, Jun. 2002.
15. M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical Review E, vol. 69, no. 2, p. 026113, 2004.
16. A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Physical Review E, vol. 70, no. 6, p. 066111, 2004.
17. 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, Oct. 2008.
18. R. Aldecoa and I. Marín, "Deciphering Network Community Structure by Surprise," PLoS ONE, vol. 6, no. 9, p. e24195, Sep. 2011.
19. S. Fortunato and M. Barthélemy, "Resolution limit in community detection," Proc. of the National Academy of Sciences, vol. 104, no. 1, pp. 36--41, 2007.
20. P. D. Hoff, A. E. Raftery, and M. S. Handcock, "Latent Space Approaches to Social Network Analysis," Journal of the American Statistical Association, vol. 97, no. 460, pp. 1090--1098, 2002.
21. M. Rosvall and C. T. Bergstrom, "Maps of random walks on complex networks reveal community structure," Proc. of the National Academy of Sciences, vol. 105, no. 4, pp. 1118--1123, Jan. 2008.
22. R. Cazabet and F. Amblard, "Simulate to Detect: A Multi-agent System for Community Detection," in Proc. of the 2011 IEEE/WIC/ACM Web Intelligence and Intelligent Agent Technology (WI-IAT), vol. 2, 2011, pp. 402--408.
23. P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, "Pocket Switched Networks and Human Mobility in Conference Environments," in Proc. of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking, ser. WDTN '05. New York, NY, USA: ACM, 2005, pp. 244--251.
24. A. Clauset, "Finding local community structure in networks," Physical Review E, vol. 72, no. 2, p. 026132, Aug. 2005.
25. 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, p. 036106, Sep. 2007.
26. R. Kanawati, "Seed-centric approaches for community detection in complex networks," in Social Computing and Social Media. Springer, 2014, pp. 197--208.
27. A.-L. Barabási and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, no. 5439, pp. 509--512, Oct. 1999.
28. L. Hubert and P. Arabie, "Comparing partitions," Journal of Classification, vol. 2, no. 1, pp. 193--218, Dec. 1985.
29. A. Strehl and J. Ghosh, "Cluster Ensembles a Knowledge Reuse Framework for Combining Multiple Partitions," Journal of Machine Learning Research, vol. 3, pp. 583--617, Mar. 2003.
30. A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Physical Review E, vol. 78, no. 4, p. 046110, Oct. 2008.
31. D. Hric, R. K. Darst, and S. Fortunato, "Community detection in networks: Structural communities versus ground truth," Physical Review E, vol. 90, no. 6, p. 062805, Dec. 2014.
32. W. Zachary, "An information flow model for conflict and fission in small groups," Journal of Anthropological Research, vol. 33, no. 4, pp. 452--473, 1977.
33. J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," Knowledge and Information Systems, vol. 42, no. 1, pp. 181--213, Oct. 2013.
34. J. Leskovec and A. Krevl, "SNAP Datasets: Stanford Large Network Dataset Collection," Jun. 2014. {Online}. Available: http://snap.stanford.edu/data

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms