Abstract
We propose here a framework to unfold the ego-centered community structure of a given node in a network. The framework is not based on the optimization of a quality function, but on the study of the irregularity of the decrease of a proximity measure. It is a practical use of the notion of multi-ego-centered community and we validate the pertinence of the approach on benchmarks and a real-world network of wikipedia pages.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The idea that there are groups of nodes which are very connected to one-another, but loosely connected to the outside.
For all experiments we used the proximity introduced in (Danisch et al. 2013a) called carryover opinion, however the framework is independent of the chosen proximity.
This quantity measures to what extent a node is near from node1 AND node2. Doing the maximum of the proximities is not relevant for our problem, since this would unfold nodes that are part of a community of node1 OR node2, but doing the product of the scores could work too.
For two sets \(A\) and \(B,\) the Jaccard similarity is given by \(Jac(A,B)=\frac{|A\cap B|}{|A\cup B|}.\)
ChessBoxing is a sport mixing Chess and Boxing in alternated rounds.
if A and B have the same size then, \(jac(A,B)>0.7\) iff A and B overlap at more than \(82.3\%.\) If \(A \subset B\) then, \(jac(A,B)>0.7\) iff \(|A|>0.7|B|.\)
References
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: theory and experiment 2008(10):P10008
Chen J, Zaiane OR, Goebel R (2009) Local community identification in social networks. In: Proceedings of the IEEE International Conference on Advances in Social Network Analysis and Mining, 2009. ASONAM’09, pp 237–242
Clauset A (2005) Finding local community structure in networks. Phys Rev E 72:026132
Danisch M, Guillaume J-L, Le Grand B (2013a) Towards multi-ego-centred communities: a node similarity approach. IJWBC 9(3):299–322
Danisch M, Guillaume J-L, Le Grand B (2013b) Unfolding ego-centered community structures with a similarity approach. Complex networks IV, Springer, Berlin, pp 145–153
Evans TS, Lambiotte R (2009) Line graphs, link partitions and overlapping communities. Phys Rev E 80:016105. doi:10.1103/PhysRevE.80.016105
Friggeri A, Chelius G, Fleury E (2011) Triangles to capture social cohesion, IEEE
Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. PNAS 99(12):7821–7826
Koren Y, North SC, Volinsky C (2007) Measuring and extracting proximity graphs in networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 1, 3, 12 ACM.
Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):016118
Luo F, Wang JZ, Promislow E (2008) Exploring local community structures in large networks. Web Intell Agent Syst 6(4):387–400
Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104
Ngonmang B, Tchuente M, Viennet E (2012) Local community identification in social networks. Parallel Process Lett 22(1):1240004
Palla G, Derenyi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818
Palla G, Farkasl IJ, Pollner P, Derenyi I, Vicsek T (2008) Fundamental statistical features and self-similar properties of tagged networks. New J Phys 10(12):123026
Sozio M, Gionis A (2010) The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 939–948, 2010, ACM
Tong H, Faloutsos C (2006) Center-piece subgraphs: problem definition and fast solutions. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 404–413, ACM
Tatti N, Gionis A (2013) Discovering nested communities. Machine learning and knowledge discovery in Databases. Springer, Berlin, 32–47
Acknowledgments
This work is supported in part by the French National Research Agency contract CODDDE ANR-13-CORD-0017-01.
Author information
Authors and Affiliations
Corresponding author
Additional information
This article is part of the Topical Collection on Social Systems as Complex Networks.
Rights and permissions
About this article
Cite this article
Danisch, M., Guillaume, JL. & Le Grand, B. Multi-ego-centered communities in practice. Soc. Netw. Anal. Min. 4, 180 (2014). https://doi.org/10.1007/s13278-014-0180-x
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13278-014-0180-x