Analysis of group evolution prediction in complex networks

Autoři: Stanisław Saganowski aff001;  Piotr Bródka aff001;  Michał Koziarski aff002;  Przemysław Kazienko aff001
Působiště autorů: Department of Computational Intelligence, Faculty of Computer Science and Management, Wrocław University of Science and Technology, Wrocław, Poland aff001;  Department of Electronics, Faculty of Computer Science, Electronics and Telecommunications, AGH University of Science and Technology, Kraków, Poland aff002
Vyšlo v časopise: PLoS ONE 14(10)
Kategorie: Research Article
doi: 10.1371/journal.pone.0224194


In the world, in which acceptance and the identification with social communities are highly desired, the ability to predict the evolution of groups over time appears to be a vital but very complex research problem. Therefore, we propose a new, adaptable, generic, and multistage method for Group Evolution Prediction (GEP) in complex networks, that facilitates reasoning about the future states of the recently discovered groups. The precise GEP modularity enabled us to carry out extensive and versatile empirical studies on many real-world complex / social networks to analyze the impact of numerous setups and parameters like time window type and size, group detection method, evolution chain length, prediction models, etc. Additionally, many new predictive features reflecting the group state at a given time have been identified and tested. Some other research problems like enriching learning evolution chains with external data have been analyzed as well.

Klíčová slova:

Community structure – Decision trees – Evolutionary immunology – Facebook – Machine learning – Network analysis – Social networks – Viral evolution


1. Zickenrott S, Angarica V, Upadhyaya B, Del Sol A. Prediction of disease–gene–drug relationships following a differential network analysis. Cell death & disease. 2017;7(1):e2040. doi: 10.1038/cddis.2015.393

2. Barabási AL, Gulbahce N, Loscalzo J. Network medicine: a network-based approach to human disease. Nature reviews genetics. 2011;12(1):56. doi: 10.1038/nrg2918 21164525

3. Wu X, Jiang R, Zhang MQ, Li S. Network-based global inference of human disease genes. Molecular systems biology. 2008;4(1):189. doi: 10.1038/msb.2008.27 18463613

4. Goh KI, Cusick ME, Valle D, Childs B, Vidal M, Barabási AL. The human disease network. Proceedings of the National Academy of Sciences. 2007;104(21):8685–8690. doi: 10.1073/pnas.0701361104

5. Pauly MD, Procario MC, Lauring AS. A novel twelve class fluctuation test reveals higher than expected mutation rates for influenza A viruses. eLife. 2017;6. doi: 10.7554/eLife.26437 28598328

6. Parvin JD, Moscona A, Pan W, Leider J, Palese P. Measurement of the mutation rates of animal viruses: influenza A virus and poliovirus type 1. Journal of virology. 1986;59(2):377–383. 3016304

7. Layne SP, Monto AS, Taubenberger JK. Pandemic influenza: an inconvenient mutation. Science. 2009;323(5921):1560–1561. doi: 10.1126/science.323.5921.1560 19299601

8. Husnain M, Toor A. The Impact of Social Network Marketing on Consumer Purchase Intention in Pakistan: Consumer Engagement as a Mediator. Asian Journal of Business and Accounting. 2017;10(1):167–199.

9. Antoniadis I, Charmantzi A. Social network analysis and social capital in marketing: theory and practical implementation. International journal of technology marketing. 2016;11(3):344–359. doi: 10.1504/IJTMKT.2016.077387

10. Guo L, Zhang M, Wang Y. Effects of customers’ psychological characteristics on their engagement behavior in company social networks. Social Behavior and Personality: an international journal. 2016;44(10):1661–1670.

11. Barhemmati N, Ahmad A. Effects of Social Network Marketing (SNM) on Consumer Purchase Behavior throughCustomer Engagement. Journal of Advanced Management Science Vol. 2015;3(4).

12. Kozinets RV, de Valck K, Wojnicki AC, Wilner SJS. Networked Narratives: Understanding Word-of-Mouth Marketing in Online Communities. Journal of Marketing. 2010;74(2):71–89.

13. Palla G, Barabási AL, Vicsek T. Quantifying social group evolution. Nature. 2007;446(7136):664. doi: 10.1038/nature05670 17410175

14. Bródka P, Saganowski S, Kazienko P. Tracking group evolution in social networks. In: International Conference on Social Informatics. Springer; 2011. p. 316–319.

15. Saganowski S, Bródka P, Kazienko P. Community Evolution. Encyclopedia of Social Network Analysis and Mining. 2017; p. 1–14. doi: 10.1007/978-1-4614-7163-9_223-1

16. Rossetti G, Cazabet R. Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR). 2018;51(2):35. doi: 10.1145/3172867

17. Goldberg MK, Magdon-Ismail M, Nambirajan S, Thompson J. Tracking and Predicting Evolution of Social Communities. In: SocialCom/PASSAT. Citeseer; 2011. p. 780–783.

18. Qin G, Yang J, Gao L, Li J. Evolution pattern discovery in dynamic networks. In: Signal Processing, Communications and Computing (ICSPCC), 2011 IEEE International Conference on. IEEE; 2011. p. 1–6.

19. Kairam SR, Wang DJ, Leskovec J. The life and death of online groups: Predicting group growth and longevity. In: Proceedings of the fifth ACM international conference on Web search and data mining. ACM; 2012. p. 673–682.

20. Si C, Jiao L, Wu J, Zhao J. A group evolving-based framework with perturbations for link prediction. Physica A: Statistical Mechanics and its Applications. 2017;475:117–128. doi: 10.1016/j.physa.2017.01.087

21. Richter Y, Yom-Tov E, Slonim N. Predicting customer churn in mobile networks through analysis of social groups. In: Proceedings of the 2010 SIAM international conference on data mining. SIAM; 2010. p. 732–741.

22. Xiao G, Zheng Z, Wang H. Evolution of Linux operating system network. Physica A: Statistical Mechanics and its Applications. 2017;466:249–258. doi: 10.1016/j.physa.2016.09.021

23. Atzmueller M, Ernst A, Krebs F, Scholz C, Stumme G. Formation and temporal evolution of social groups during coffee breaks. In: Big Data Analytics in the Social and Ubiquitous Context. Springer; 2014. p. 90–108.

24. Bródka P, Kazienko P, Kołoszczyk B. Predicting group evolution in the social network. Social Informatics. 2012; p. 54–67.

25. Bródka P, Saganowski S, Kazienko P. GED: the method for group evolution discovery in social networks. Social Network Analysis and Mining. 2013;3(1):1–14. doi: 10.1007/s13278-012-0058-8

26. Gliwa B, Saganowski S, Zygmunt A, Bródka P, Kazienko P, Kozak J. Identification of group changes in blogosphere. In: Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012). IEEE Computer Society; 2012. p. 1201–1206.

27. Gliwa B, Bródka P, Zygmunt A, Saganowski S, Kazienko P, Koźlak J. Different Approaches to Community Evolution Prediction in Blogosphere. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ASONAM’13. New York, NY, USA: ACM; 2013. p. 1291–1298. Available from:

28. Ilhan N, Oguducu IG. Community event prediction in dynamic social networks. In: Machine Learning and Applications (ICMLA), 2013 12th International Conference on. vol. 1. IEEE; 2013. p. 191–196.

29. Takaffoli M, Rabbany R, Zaïane OR. Community evolution prediction in dynamic social networks. In: Advances in Social Networks Analysis and Mining (ASONAM), 2014 IEEE/ACM International Conference on. IEEE; 2014. p. 9–16.

30. Saganowski S, Gliwa B, Bródka P, Zygmunt A, Kazienko P, Koźlak J. Predicting community evolution in social networks. Entropy. 2015;17(5):3053–3096. doi: 10.3390/e17053053

31. Diakidis G, Karna D, Fasarakis-Hilliard D, Vogiatzis D, Paliouras G. Predicting the evolution of communities in social networks. In: Proceedings of the 5th International Conference on Web Intelligence, Mining and Semantics. ACM; 2015. p. 1.

32. İlhan N, Öğüdücü ŞG. Feature identification for predicting community evolution in dynamic social networks. Engineering Applications of Artificial Intelligence. 2016;55:202–218. doi: 10.1016/j.engappai.2016.06.003

33. Pavlopoulou MEG, Tzortzis G, Vogiatzis D, Paliouras G. Predicting the evolution of communities in social networks using structural and temporal features. In: Semantic and Social Media Adaptation and Personalization (SMAP), 2017 12th International Workshop on. IEEE; 2017. p. 40–45.

34. Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005;435(7043):814–818. doi: 10.1038/nature03607 15944704

35. Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences. 2008;105(4):1118–1123. doi: 10.1073/pnas.0706851105

36. He Z, Tajeuna EG, Wang S, Bouguessa M. A Comparative Study of Different Approaches for Tracking Communities in Evolving Social Networks. In: Data Science and Advanced Analytics (DSAA), 2017 IEEE International Conference on. IEEE; 2017. p. 89–98.

37. Hopcroft J, Khan O, Kulis B, Selman B. Tracking evolving communities in large linked networks. Proceedings of the National Academy of Sciences. 2004;101(suppl 1):5249–5253. doi: 10.1073/pnas.0307750100

38. Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the american statistical association. 1937;32(200):675–701. doi: 10.1080/01621459.1937.10503522

39. Shaffer JP. Modified sequentially rejective multiple test procedures. Journal of the American Statistical Association. 1986;81(395):826–831. doi: 10.1080/01621459.1986.10478341

40. Barzel B, Barabási AL. Universality in network dynamics. Nature physics. 2013;9:673–681. doi: 10.1038/nphys2741

41. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU. Complex networks: Structure and dynamics. Physics Reports. 2006;424(4):175–308.

42. Dezsö Z, Almaas E, Lukács A, Rácz B, Szakadát I, Barabási AL. Dynamics of information access on the web. Phys Rev E. 2006;73:066132. doi: 10.1103/PhysRevE.73.066132

43. Kessler MM. Bibliographic coupling between scientific papers. American Documentation. 1963;14(1):10–25. doi: 10.1002/asi.5090140103

44. Small H. Co-citation in the scientific literature: A new measure of the relationship between two documents. Journal of the American Society for Information Science. 1973;24(4):265–269. doi: 10.1002/asi.4630240406

45. Böde C, Kovács IA, Szalay MS, Palotai R, Korcsmáros T, Csermely P. Network analysis of protein dynamics. FEBS Letters. 2007;581(15):2776–2782. doi: 10.1016/j.febslet.2007.05.021 17531981

46. Barabási AL, Gulbahce N, Loscalzo J. Network medicine: a network-based approach to human disease. Nature reviews Genetics. 2011;12(1):56–68. doi: 10.1038/nrg2918 21164525

47. Bartusiak R, Łukasz Augustyniak, Kajdanowicz T, Kazienko P, Piasecki M. WordNet2Vec: Corpora agnostic word vectorization method. Neurocomputing. 2019;326-327:141–150.

48. Indyk W, Kajdanowicz T, Kazienko P. Relational large scale multi-label classification method for video categorization. Multimedia Tools and Applications. 2013;65(1):63–74. doi: 10.1007/s11042-012-1149-2

Článek vyšel v časopise


2019 Číslo 10