Community Identification in Dynamic Heterogeneous Networks

Arizona State University, Computer Science and Engineering, Data Mining and Machine Learning

Overview

With social media, people can connect to each other more conveniently than ever. In some social networking sites, entities other than human beings can also be involved. For instance, in YouTube, a user can upload a video and another user can tag it. In other words, the users, videos, and tags are knit together in the same network. The ``actors'' in the network are not homogeneous. Furthermore, examining activities of users, we can observe different interaction networks between the same set of actors. Take YouTube as an example. A user can become a friend of another user; he can also subscribe to another user. The existence of different relations suggests that the interactions between actors are not homogeneous. Networks involving heterogeneous actors or interactions are referred as heterogeneous networks. Accordingly, heterogeneous networks can be categorized in two different types:

Multi-Mode Network: A multi-mode network involves heterogeneous actors. Each mode represents one type of entities.
Multi-Dimensional Network: A multi-dimensional network has multiple types of interactions (relations) between the same set of users.

How to identify communities in dynamic heterogeneous networks is a challenging task. Here, we list some of our published works as well as the data sets collected from social media for evaluation purpose.

Downloads

YouTube data used in [3]. The package contains a README file that explains the dataset.
Script for the PMM method. [PMM code]

The dataset and script are freely available for academic and research use. The use of the dataset can be referenced to the following publication:

@INPROCEEDINGS{Tang-etal09-ICDM, 
  author = {Lei Tang and Xufei Wang and Huan Liu}, 
  title = {Uncovering Groups via Heterogeneous Interaction Analysis}, 
  booktitle = {ICDM '09: Proceedings of IEEE International Conference on Data Mining},
  year = {2009}, 
  pages = {503-512}, 
}

DBLP data and Enron email corpus used in [1].
Script to capture community evolution in dynamic multi-mode networks [code]

The use of the dataset and code can be referenced to the following publication:

@inproceedings{Tang-Liu08-KDD,
 author = {Tang, Lei and Liu, Huan and Zhang, Jianping and Nazeri, Zohreh},
 title = {Community evolution in dynamic multi-mode networks},
 booktitle = {KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining},
 year = {2008},
 isbn = {978-1-60558-193-4},
 pages = {677--685},
 location = {Las Vegas, Nevada, USA},
 doi = {http://doi.acm.org/10.1145/1401890.1401972},
 publisher = {ACM},
 address = {New York, NY, USA},
 }

People

Lei Tang
Huan Liu
Xufei Wang

Tutorial

Huan Liu, Lei Tang, and Nitin Agarwal, "Tutorial: Community Detection and Behavior Study for Social Computing", presented at IEEE Infernational Conference on Social Computing (SocialCom'09), 2009

References

[7] Lei Tang, Xufei Wang and Huan Liu. "Community Detection via Heterogeneous Interaction Analysis", Journal of Data Mining and Knowledge Discovery (DMKD), 2011.

[6] Xufei Wang, Lei Tang, Huiji Gao and Huan Liu. "Discovering Overlapping Groups in Social Media", Proceedings of IEEE International Conference on Data Mining (ICDM'10), 2010.

[5] Lei Tang, Huan Liu and Jianping Zhang. " Identifying Evolving Groups in Dynamic Multi-Mode Networks", in Transactions on Knowledge and Data Engineering, to appear.

[4] Lei Tang, and Huan Liu. "Understanding Group Structures and Properties in Social Media" (preprint), in Link Mining: Models, Algorithms and Applications, Editors: Christos Faloutsos, Jiawei Han and Philip S. Yu, in press.

[3] Lei Tang, Xufei Wang and Huan Liu. "Uncovering Groups via Heterogeneous Interaction Analysis", in Proceedings of IEEE International Conference on Data Mining (ICDM'09), 2009.

[2] Lei Tang and Huan Liu. "Uncovering Cross-Dimension Group Structures in Multi-Dimensional Networks", in SDM workshop on Analysis of Dynamic Networks, 2009. (A formal extension of this work is publised in ICDM'09).

[1] Lei Tang, Huan Liu, Jianping Zhang, and Zohreh Nazeri. "Community Evolution in Dynamic Multi-Mode Networks", in Proceedings of the 14th ACM SIGKDD International Conference on Discovery and Data Mining (KDD'08), pp 677-685, August 24-27, 2008. Las Vegas, Neveda.

Acknowledgements

This project is sponsored by MITRE (2008), ONR-N000140810477 and AFOSR-FA95500810132.