Alexandra Lee
ABSTRACT
Many algorithms have been created to automatically detect community structures in social networks. These algorithms have been studied from the perspective of optimisation extensively. However, which community finding algorithm most closely matches the human notion of communities? In this paper, we conduct a user study to address this question. In our experiment, users collected their own Facebook network and manually annotated it, indicating their social communities. Given this annotation, we run state-of-the-art community finding algorithms on the network and use Normalised Mutual Information (NMI) to compare annotated communities with automatically detected ones. Our results show that the Infomap algorithm has the greatest similarity to user defined communities, with Girvan-Newman and Louvain algorithms also performing well.
- R. Aldecoa and I. Marín. 2013. Exploring the limits of community detection strategies in complex networks. Scientific Reports 3 (2013), 2216 EP.Google Scholar
- V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, 10 (Oct. 2008), P10008. DOI:http://dx.doi.org/10.1088/1742-5468/2008/10/P10008Google ScholarCross Ref
- M. Bostock, V. Ogievetsky, and J. Heer. 2011. D3 Data-Driven Documents. IEEE Transactions on Visualization and Computer Graphics 17, 12 (Dec. 2011), 2301--2309. DOI: http://dx.doi.org/10.1109/TVCG.2011.185 Google ScholarDigital Library
- T. Dwyer, L. Bongshin, D. Fisher, K.I. Quinn, P. Isenberg, G. Robertson, and C. North. 2009. A Comparison of User-Generated and Automatic Graph Layouts. Visualization and Computer Graphics, IEEE Transactions on 15, 6 (2009), 961--968. Google ScholarDigital Library
- P.A. Estevez, M. Tesmer, C.A. Perez, and J.M. Zurada. 2009. Normalized Mutual Information Feature Selection. Neural Networks, IEEE Transactions on 20, 2 (Feb 2009), 189--201. DOI: http://dx.doi.org/10.1109/TNN.2008.2005601 Google ScholarDigital Library
- M. Girvan and M. E. J. Newman. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 12 (2002), 7821--7826. DOI: http://dx.doi.org/10.1073/pnas.122653799Google ScholarCross Ref
- D. Hansen, B. Shneiderman, and M. A. Smith. 2010. Analyzing Social Media Networks with NodeXL: Insights from a Connected World. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
- B. Hogan, J. A. Carrasco, and B. Wellman. 2007. Visualizing personal networks: working with participant-aided sociograms. Field Methods 19, 2 (2007), 116--144.Google ScholarCross Ref
- A. Lancichinetti and S. Fortunato. 2009. Community detection algorithms: A comparative analysis. Phys. Rev. E 80 (Nov 2009), 056117. Issue 5. DOI: http://dx.doi.org/10.1103/PhysRevE.80.056117Google ScholarCross Ref
- A. Lancichinetti, S. Fortunato, and F. Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78 (Oct 2008), 046110. Issue 4. DOI: http://dx.doi.org/10.1103/PhysRevE.78.046110Google ScholarCross Ref
- A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato. 2011. Finding Statistically Significant Communities in Networks. PLoS ONE 6, 4 (04 2011), e18961. DOI: http://dx.doi.org/10.1371/journal.pone.0018961Google Scholar
- G. K. Orman, V. Labatut, and H. Cherifi. 2013. Towards Realistic Artificial Benchmark for Community Detection Algorithms Evaluation. Int. J. Web Based Communities 9, 3 (June 2013), 349--370. DOI: http://dx.doi.org/10.1504/IJWBC.2013.054908 Google ScholarDigital Library
- G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043 (09 06 2005), 814--818. http://dx.doi.org/10.1038/nature03607Google Scholar
- H.C. Purchase, C. Pilcher, and B. Plimmer. 2012. Graph Drawing Aesthetics -- Created by Users, Not Algorithms. Visualization and Computer Graphics, IEEE Transactions on 18, 1 (Jan 2012), 81--92. DOI: http://dx.doi.org/10.1109/TVCG.2010.269 Google ScholarDigital Library
- H. C. Purchase. 2013. Sketched Graph Drawing: A Lesson in Empirical Studies. In Proc. of Graph Drawing (GD '13). LNCS, Vol. 8242. 232--243.Google Scholar
- H. C. Purchase. 2014. A healthy critical attitude: Revisiting the results of a graph drawing study. Journal of Graph Algorithms and Applications 18, 2 (2014), 281--311. DOI: http://dx.doi.org/10.7155/jgaa.00323Google ScholarCross Ref
- M. Rosvall, D. Axelsson, and C. T. Bergstrom. 2009. The map equation. The European Physical Journal Special Topics 178, 1 (2009), 13--23. DOI: http://dx.doi.org/10.1140/epjst/e2010-01179--1Google ScholarCross Ref
- M. Rosvall and C. T. Bergstrom. 2007. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences 104, 18 (2007), 7327--7331. DOI: http://dx.doi.org/10.1073/pnas.0611034104Google ScholarCross Ref
- F. van Ham and B. Rogowitz. 2008. Perceptual Organization in User-Generated Graph Layouts. Visualization and Computer Graphics, IEEE Transactions on 14, 6 (Nov 2008), 1333--1339. DOI: http://dx.doi.org/10.1109/TVCG.2008.155 Google ScholarDigital Library
- E. Ziv, M. Middendorf, and C. H. Wiggins. 2005. Information-theoretic approach to network modularity. Physical Review E 71(4 Pt 2) (Apr 2005), 046117. Epub 2005 Apr 14. http://link.aps.org/abstract/PRE/v71/e046117Google Scholar
Index Terms
- Communities Found by Users -- not Algorithms: Comparing Human and Algorithmically Generated Communities
Recommendations
IJQwerty: What Difference Does One Key Change Make? Gesture Typing Keyboard Optimization Bounded by One Key Position Change from Qwerty
CHI '16: Proceedings of the 2016 CHI Conference on Human Factors in Computing SystemsDespite of a significant body of research in optimizing the virtual keyboard layout, none of them has gained large adoption, primarily due to the steep learning curve. To address this learning problem, we introduced three types of Qwerty constraints, ...
First I "like" it, then I hide it: Folk Theories of Social Feeds
CHI '16: Proceedings of the 2016 CHI Conference on Human Factors in Computing SystemsMany online platforms use curation algorithms that are opaque to the user. Recent work suggests that discovering a filtering algorithm's existence in a curated feed influences user experience, but it remains unclear how users reason about the operation ...
Accounting for Taste: Ranking Curators and Content in Social Networks
CHI '16: Proceedings of the 2016 CHI Conference on Human Factors in Computing SystemsRanking users in social networks is a well-studied problem, typically solved by algorithms that leverage network structure to identify influential users and recommend people to follow. In the last decade, however, curation --- users sharing and ...
Comments