Understanding evolving group structures in time-varying networks

ABSTRACT

This paper presents a framework for identifying persistent groups and individuals across multiple time granularities in dynamic graphs. Understanding the longevity of groups and the relevance of individuals within a group is important in many fields, including sociology, biology, economics, psychology, and political science. Different clustering algorithms have been proposed for static and dynamic graphs. However, using the clustering results to understand the changing dynamics of groups can be difficult. In order to better understand how groups evolve and the level of cohesion within these groups, we propose a holistic dynamic clustering framework that allows the user to adjust the underlying algorithms for clustering nodes in a graph that changes over time and then use the final clusters to produce a time hierarchy that highlights the groups and individuals persistent during different time periods. We test our framework and algorithm both on synthetic and real world data. Our findings indicate that our approach not only yields highly accurate results, but also detects unexpected variations in group structure.

References

1. M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821--7826, 2002.
2. M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577--8582, 2006.
3. A. Banerjee, S. Basu, and S. Merugu, "Multi-way clustering on relation graphs," in SDM, 2006, pp. 145--156.
4. B. Long, X. Wu, Z. M. Zhang, and P. S. Yu, "Unsupervised learning on k-partite graphs," in KDD, 2006, pp. 317--326.
5. G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, p. 814, 2005.
6. H. Shen, X. Cheng, K. Cai, and M.-B. Hu, "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, vol. 388, no. 8, pp. 1706--1712, 2009.
7. Y. Zhou, H. Cheng, and J. X. Yu, "Graph clustering based on structural/attribute similarities," in VLDB, 2009, pp. 718--729.
8. C. Tantipathananandh, T. Berger-Wolf, and D. Kempe, "A framework for community identification in dynamic social networks," in KDD, 2007, pp. 717--726.
9. G. Palla, A. Barabasi, and T. Vicsek, "Quantifying social group evolution," Nature, vol. 446, no. 7136, pp. 664--667, 2007.
10. C. Aggarwal and P. Yu, "Online analysis of community evolution in data streams," in SDM, 2005, pp. 56--67.
11. R. Görke, T. Hartmann, and D. Wagner, "Dynamic graph clustering using minimum-cut trees," Algorithms and Data Structures, pp. 339--350, 2009.
12. J. Hopcroft, O. Khan, B. Kulis, and B. Selman, "Tracking evolving communities in large linked networks," Proceedings of the National Academy of Sciences, vol. 101, no. Supplemental 1, pp. 5249--5253, 2004.
13. J. Sun, C. Faloutsos, S. Papadimitriou, and P. Yu, "Graphscope: parameter-free mining of large time-evolving graphs," in KDD, 2007, pp. 687--696.
14. T. Warren Liao, "Clustering of time series data - a survey," Pattern Recognition, vol. 38, no. 11, pp. 1857--1874, 2005.
15. C. Antunes and A. Oliveira, "Temporal data mining: An overview," in KDD Workshop on Temporal Data Mining, 2001, pp. 1--13.
16. S. Das, A. Abraham, and A. Konar, "Automatic clustering using an improved differential evolution algorithm," IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 38, no. 1, pp. 218--237, 2008.
17. D. Chakrabarti, R. Kumar, and A. Tomkins, "Evolutionary clustering," in KDD, 2006, pp. 554--560.
18. J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, "Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication," in PKDD, 2005, pp. 133--145.
19. L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, "Group formation in large social networks: membership, growth, and evolution," in KDD, 2006, pp. 44--54.
20. P. Bródka, S. Saganowski, and P. Kazienko, "Ged: the method for group evolution discovery in social networks," Social Network Analysis and Mining, pp. 1--14, 2012.
21. S. Asur, S. Parthasarathy, and D. Ucar, "An event-based framework for characterizing the evolutionary behavior of interaction graphs," in KDD, 2007, pp. 913--921.
22. L. Friedland and D. Jensen, "Finding tribes: identifying close-knit individuals from employment patterns," in KDD, 2007, pp. 290--299.
23. H. Habiba, Y. Yu, T. Berger-Wolf, and J. Saia, "Finding spread blockers in dynamic networks," in SNAKDD, pp. 55--76.
24. H. Sharara, L. Singh, L. Getoor, and J. Mann, "Finding prominent actors in dynamic affiliation networks," Human Journal, vol. 1, no. 1, pp. 1--14, 2012.
25. J. Han and M. Kamber, Data mining: concepts and techniques, 2006.
26. "Shark bay dolphin project," http://www.monkeymiadolphins.org.

Index Terms

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Web-based interaction

• Information systems

  • Information retrieval

    • Document representation

  • Information systems applications

    • Data mining