Methods for Clustering Multi-Layer Graphs in Mobile Networks

Clustering on graphs has been studied extensively for years due to its numerous applications. However, in contrast to the classic problems, clustering in mobile and online social networks brings new challenges. In these scenarios, it is common that observational data contains multiple modalities of information reflecting different aspects of human behavior and social interactions. These interactions may be represented by a multi-layer graph that share the same set of vertices representing users, while having different layers representing different relationships among users. Intuitively, each graph should contribute to a better understanding of the underlying clusters from its own angle. It may be expected that a proper combination of the multiple graphs could lead to a better unified clustering of users' behavior and their social interactions. In this work we consider different methods to combine multi-layer graphs. In particular, we propose an efficient way to combine spectra of multiple graphs to form a “common spectrum”. To verify the suggested approach we tested it using mobile datasets. Also we compare the proposed approach with community detection methods based on modularity maximization over single and multiple layer graphs.

Presented at:
Interdisciplinary Workshop on Information and Decision in Social Networks, MIT, Cambridge, Massachusetts, USA, May 31-June 1, 2011

 Record created 2011-04-20, last modified 2018-03-18

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)