Content area
Full Text
Data Min Knowl Disc (2013) 27:294320
DOI 10.1007/s10618-013-0331-0
Received: 16 November 2012 / Accepted: 26 June 2013 / Published online: 18 July 2013 The Author(s) 2013
Abstract Community discovery in complex networks is the problem of detecting, for each node of the network, its membership to one of more groups of nodes, the communities, that are densely connected, or highly interactive, or, more in general, similar, according to a similarity function. So far, the problem has been widely studied in monodimensional networks, i.e. networks where only one connection between two entities may exist. However, real networks are often multidimensional, i.e., multiple connections between any two nodes may exist, either reecting different kinds of relationships, or representing different values of the same type of tie. In this context, the problem of community discovery has to be redened, taking into account multidimensional structure of the graph. We dene a new concept of community that groups together nodes sharing memberships to the same monodimensional communities in the different single dimensions. As we show, such communities are meaningful and able to group nodes even if they might not be connected in any of the monodimensional networks. We devise frequent pAttern mining-BAsed Community discoverer in mUltidimensional networkS (ABACUS), an algorithm that is able to extract multidimensional communities based on the extraction of frequent closed itemsets from monodimensional community memberships. Experiments on two different real multidimensional networks conrm the meaningfulness of the introduced concepts, and
Responsible editor: Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, Filip Zelezny.
M. Berlingerio (B) F. Pinelli F. Calabrese
IBM Research, Dublin, Irelande-mail: [email protected]
F. Pinellie-mail: [email protected]
F. Calabresee-mail: [email protected]
ABACUS: frequent pAttern mining-BAsed Community discovery in mUltidimensional networkS
Michele Berlingerio Fabio Pinelli
Francesco Calabrese
123
ABACUS: community discovery in multidimensional networks 295
open the way for a new class of algorithms for community discovery that do not rely on the dense connections among nodes.
Keywords Community discovery Multidimensional networks
Social network analysis
1 Introduction
Inspired by real-world scenarios such as social networks, technology networks, the Web, biological networks, and so on, in the last years, wide, multidisciplinary, and extensive research has been devoted to the extraction of non trivial knowledge from networks. Predicting future links among the nodes or actors of a network (Bringmann et al. 2010),...