Image Processing Reference
In-Depth Information
3
Multiple-Membership Communities Detection
and Its Applications for Mobile Networks
Nikolai Nefedov
Nokia Research Center
ISI Lab, Swiss Federal Institute of Technology Zurich (ETHZ)
Switzerland
1. Introduction
The recent progress in wireless technology and growing spread of smart phones equipped
with various sensors make it possible to record real-world rich-content data and compliment
it with on-line processing. Depending on the application, mobile data processing could
help people to enrich their social interactions and improve environmental and personal
health awareness. At the same time, mobile sensing data could help service providers to
understand better human behavior and its dynamics, identify complex patterns of users'
mobility, and to develop various service-centric and user-centric mobile applications and
services on-demand. One of the first steps in analysis of rich-content mobile datasets is to find
an underlying structure of users' interactions and its dynamics by clustering data according
to some similarity measures.
Classification and clustering (finding groups of similar elements in data) are well-known
problems which arise in many fields of sciences, e.g., (Albert & Barabási, 2002; Flake et al,
2002; Wasserman & Faust, 1994). In cases when objects are characterized by vectors of
attributes, a number of efficient algorithms to find groups of similar objects based on a metric
between the attribute vectors are developed. On the other hand, if data are given in the
relational format (causality or dependency relations), e.g., as a network consisting of N nodes
and E edges representing some relation between the nodes, then the problem of finding
similar elements corresponds to detection of communities, i.e., groups of nodes which are
interconnected more densely among themselves than with the rest of the network.
The growing interest to the problem of community detection was triggered by the introduction
of a new clustering measure called modularity (Girvan & Newman, 2002; 2004). The
modularity maximization is known as the NP-problem and currently a number of different
sub-optimal algorithms are proposed, e.g., see (Fortunato, 2011) and references within.
However, most of these methods address network partitions into disjoint communities.
On the other hand, in practice communities are often overlapping. It is especially visible
in social networks, where only limited information is available and people are affiliated
to different groups, depending on professional activities, family status, hobbies, and etc.
Furthermore, social interactions are reflected in multiple dimensions, such as users activities,
local proximities, geo-locations and etc. These multi-dimensional traces may be presented as
multi-layer graphs. It raises the problem of overlapping communities detection at different
Search WWH ::




Custom Search