Abstract
The purpose of this paper is to handle the disappearance of a group of nodes in a social network. The quality of the information flow is used as a key performance indicator to conduct network changes after group disappearance. Nodes as well as node sets are first classified into categories (critical and non-critical nodes, and scattered, contiguous and hybrid groups) and then analyzed according to two distinct perspectives: the network as a whole or its identified communities. Finally, algorithms are devised to manage group disappearance according to different cases. New links are added in a parsimonious way and a possible substitute for a leaving group is found based on the adage “birds of a feather flock together” and the homophily principle. This means that new links (e.g., relationships) and a potential substitute are found only between individuals that share common characteristics such as beliefs, values, and education, i.e., individuals that are more likely neighbors of the leaving node or group. To validate our approach, an empirical study is conducted using various kinds of data sets and a set of criteria. The results show the benefits of our solution in terms of response time, number of added links and metrics of the overall network topology.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aggarwal CC, Khan A, Yan X (2011) On flow authority discovery in social networks. In: SDM, pp 522–533
Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512
Borgatti SP (2006) Identifying sets of key players in a social network. Comput Math Organ Theory 12(1):21–34
Carrington PJ (2005) Models and methods in social network analysis. Structural analysis in the social sciences. Cambridge University Press, Cambridge
Everett MG, Borgatti SP (2005) Extended centrality. In: Carrington PJ (ed) Models and methods in social network analysis, Cambridge University Press, Cambridge, pp 57–76
Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. doi:10.1016/j.physrep.2009.11.002
Gilbert F, Simonetto P, Zaidi F, Jourdan F, Bourqui R (2011) Communities and hierarchical structures in dynamic social networks: analysis and visualization. Soc Netw Anal Min 1(2):83–95
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci USA 99(12):7821–7826
Hanneman R, Riddle M (2005) Introduction to social network methods. http://faculty.ucr.edu/hanneman/nettext/
Hussain DMA, Ahmed Z (2008) Dynamical adaptation in terrorist cells/networks. In: SCSS, vol 2. pp 557–562
Knoke D, Yang S (2008) Social network analysis, 2nd edn. Sage, London
Kuhlman CJ, Kumar VSA, Marathe MV, Ravi SS, Rosenkrantz DJ (2010) Finding critical nodes for inhibiting diffusion of complex contagions in social networks. In: ECML/PKDD, vol 2. pp 111–127
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):1–41. doi:10.1145/1217299.1217301
Li CT, Hsieh HP, Lin SD, Shan MK (2012) Finding influential seed successors in social networks. In: Proceedings of the 21st international conference companion on World Wide Web, WWW ’12 Companion, pp 557–558
Liben-Nowell D, Kleinberg J (2003) The link prediction problem for social networks. In: CIKM ’03: Proceedings of the twelfth international conference on Information and knowledge management, ACM, pp 556–559
Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inf Sci Technol 58(7):1019–1031
Missaoui R, Negre E, Anggraini D, Vaillancourt J (2012) Network restructuring after a node removal. Int J Web Eng Technol (IJWET) 7(4):4–26
Negre E, Missaoui R, Vaillancourt J (2011) Predicting a social network structure once a node is deleted. In: ASONAM, pp 297–304
NetworkX library (2011) http://networkx.lanl.gov/
Newman MEJ (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066–133
Ortiz-Arroyo D (2010) Discovering sets of key players in social networks. In: Abraham A, Hassanien AE, Snášel V (eds) Computational social network analysis, computer communications and networks. Springer, London, pp 27–47
Petersen RR, Rhodes CJ, Wiil UK (2011) Node removal in criminal networks. In: EISIC, pp 360–365
PiCloud (2012) http://www.picloud.com/
Qi X, Duval RD, Christensen K, Fuller E, Spahiu A, Wu Q, Wu Y, Tang W, Zhang C (2013) Terrorist networks, network energy and node removal: a new measure of centrality based on Laplacian energy. Soc Netw 2(1):19–31
Rees BS, Gallagher KB (2012) Overlapping community detection using a community optimized graph swarm. Soc Netw Anal Min 2(4):405–417
Sarr I, Missaoui R (2012) Managing node disappearance based on information flow in social networks. Soc Netw Anal Min J (SNAM), pp 1–13. doi:10.1007/s13278-012-0071-y
Sarr I, Missaoui R, Lalande R (2012) Dealing with the disappearance of an actor set in social networks. In: ASONAM, pp 492–499
Stanford dataset (2003) http://snap.stanford.edu/data/ca-HepTh.html
Stanford dataset (2009) http://snap.stanford.edu/data/as.html
Vasudevan M, Deo N (2012) Efficient community identification in complex networks. Soc Netw Anal Min 2(4):345–359
Wasserman S, Faust K (1994) Social network analysis: methods and applications, 1st edn. Structural analysis in the social sciences, Cambridge University Press, Cambridge
Xie J, Kelley S, Szymanski BK (2011) Overlapping community detection in networks: the state of the art and comparative study. CoRR abs/1110.5813
Acknowledgments
I. Sarr is grateful to “Programme canadien de bourses de la Francophonie” (PCBF) of the Canadian International Development Agency (CIDA) for the postdoctoral fellowship while R. Missaoui acknowledges the financial support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sarr, I., Missaoui, R. & Lalande, R. Group disappearance in social networks with communities. Soc. Netw. Anal. Min. 3, 651–665 (2013). https://doi.org/10.1007/s13278-013-0112-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13278-013-0112-1