Characterizing and predicting community members from evolutionary and heterogeneous networks

ABSTRACT

Mining different types of communities from web data have attracted a lot of research efforts in recent years. However, none of the existing community mining techniques has taken into account both the dynamic as well as heterogeneous nature of web data. In this paper, we propose to characterize and predict community members from the evolution of heterogeneous web data. We first propose a general framework for analyzing the evolution of heterogeneous networks. Then, the academic network, which is extracted from 1 million computer science papers, is used as an example to illustrate the framework. Finally, two example applications of the academic network are presented. Experimental results with a real and very large heterogeneous academic network show that our proposed framework can produce good results in terms of community member recommendation. Also, novel knowledge and insights can be gained by analyzing the community evolution pattern.

REFERENCES

• 1: L. Adamic and E. Adar. Friends and neighbors on the web. In TR HP, 2001.
• 2: Sitaram Asur , Srinivasan Parthasarathy , Duygu Ucar, An event-based framework for characterizing the evolutionary behavior of interaction graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281290]
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 4: A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 5: Tanja Falkowski , Jorg Bartelheimer , Myra Spiliopoulou, Mining and Visualizing the Evolution of Subgroups in Social Networks, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.52-58, December 18-22, 2006 [doi>10.1109/WI.2006.118]
• 6: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 7: C. M. Fonseca and P. J. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms - Part I: A unified formulation. In IEEE TSMC, 28(1):26--37, 1998.
• 8: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 9: John Hopcroft , Omar Khan , Brian Kulis , Bart Selman, Natural communities in large linked networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956816]
• 10: Hidehiko Ino , Mineichi Kudo , Atsuyoshi Nakamura, Partitioning of Web graphs by community topology, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060841]
• 11: Jon M. Kleinberg, Hubs, authorities, and communities, ACM Computing Surveys (CSUR), v.31 n.4es, Dec. 1999 [doi>10.1145/345966.345982]
• 12: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the bursty evolution of blogspace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775233]
• 13: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 14: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 15: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 16: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 17: Yu-Ru Lin , Hari Sundaram , Yun Chi , Junichi Tatemura , Belle L. Tseng, Blog Community Discovery and Evolution Based on Mutual Awareness Expansion, Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, p.48-56, November 02-05, 2007 [doi>10.1109/WI.2007.30]
• 18: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2-3, p.161-179, March-May 1995
• 19: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 20: F. Osareh. Bibliometrics, citation analysis and co-citation analysis: A review of literature I. Libri 46 (September 1996), 149--158, 1996.
• 21: Chayant Tantipathananandh , Tanya Berger-Wolf , David Kempe, A framework for community identification in dynamic social networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281269]
• 22: Masashi Toyoda , Masaru Kitsuregawa, Extracting evolution of web communities from a series of web archives, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900059]
• 23: W.-J. Zhou, J.-R. Wen, W.-Y. Ma, and H.-J. Zhang. A concentric model for community mining in graph structures. TR, Microsoft Research, 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation

Keywords:
evolutionary web community, heterogeneous network, member characterization, member prediction