Tang et al., TRANSACTION ON KNOWLEDGE AND DATA ENGINEERING 2010

Citation

Authors: Lei Tang, Huan Liu, and Jianping Zhang

Title: Identifying Evolving Groups in Dynamic Multi-Mode Networks

Journal: TRANSACTION ON KNOWLEDGE AND DATA ENGINEERING 2010

Online version

Paper: [1]

Summary

This paper tries to identify communities in multi-mode networks (networks which contain heterogeneous types of actors and different interactions between these actors). Other goal of this paper is to detect and identify the changes between community memberships and the interactions between actors during time. The authors used a temporally-regularized framework to solve this problem. They examined their framework on both synthetic and real datasets and obtained good results in efficiency and generality of their method.

Brief description of the method

In this paper the authors have used block model approximation to approximate the transaction matrix between two modes at each time, based on group interaction between modes at that time and membership of each mode in each community. Then an error function has been used to identify the error between these two values. The authors have introduced different variations of this model based on various requirements. The defined model a are:

• community detection with network sequence: which includes snapshots of the network in different timestamps in the error function.

• community detection with temporal regularization: in this variation, the similarity between consequtive snapshots is added to the error calculation. Since we think that a network changes gradually during time and as a result, when the snapshots are successive, they should be similar in community membership.

To obtain the interaction matrix between modes and minimizing the error function, a spectral mod del is applied based on the error definition and its constraints which allows the authors to do so. As a result, the solving algorithm is defined as finding out the important features of data and then applying iterative LSA on these features.

Other variations of the algorithm such as including actor attributes, higher order temporal regularization, and within mode interactions also have Ben defined in the paper.

Experimental result

For experiments on synthetic data, they used NMI (normalized mutual information) to show that the detected communities are similar to the actual ones. Since there is no gold standard for the real data, they defined the clustering algorithm measure and used that to research on it. They also have done a manual looking at the dataset and algorithm results and found out their algorithm can detect the changes during time for network in addition to community detection.

Dataset used

Enron data

DBLP data