Differential Flattening: A Novel Framework for Community Detection in Multi-Layer Graphs

A multi-layer graph consists of multiple layers of weighted graphs, where the multiple layers represent the different aspects of relationships. Considering multiple aspects (i.e., layers) together is essential to achieve a comprehensive and consolidated view. In this article, we propose a novel framework of differential flattening, which facilitates the analysis of multi-layer graphs, and apply this framework to community detection. Differential flattening merges multiple graphs into a single graph such that the graph structure with the maximum clustering coefficient is obtained from the single graph. It has two distinct features compared with existing approaches. First, dealing with multiple layers is done independently of a specific community detection algorithm, whereas previous approaches rely on a specific algorithm. Thus, any algorithm for a single graph becomes applicable to multi-layer graphs. Second, the contribution of each layer to the single graph is determined automatically for the maximum clustering coefficient. Since differential flattening is formulated by an optimization problem, the optimal solution is easily obtained by well-known algorithms such as interior point methods. Extensive experiments were conducted using the Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks as well as theDBLP, 20 Newsgroups, and MIT Reality Mining networks. The results show that our approach of differential flattening leads to discovery of higher-quality communities than baseline approaches and the state-of-the-art algorithms.
Publisher
ASSOC COMPUTING MACHINERY
Issue Date
2017-01
Language
English
Citation

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY, v.8, no.2

ISSN
2157-6904
DOI
10.1145/2898362
URI
http://hdl.handle.net/10203/218222
Appears in Collection
KSE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 206
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0