Image Processing Reference
In-Depth Information
hierarchical levels at single and multi-layer graphs.
In this chapter we present a framework for multi-membership communities detection
in dynamical multi-layer graphs and its applications for missing (or hidden) link
predictions/recommendations based on the network topology. In particular, we use
modularity maximization with a fast greedy search (Newman, 2004) extended with a random
walk approach (Lambiotte et al, 2009) to detect multi-resolution communities beyond and
below the resolution provided by max -modularity. We generalize a random walk approach
to a coupled dynamic systems (Arenas et al, 2006) and then extend it with dynamical links
update to make predictions beyond the given topology. In particular, we introduce attractive
and repulsive coupling that allow us to detect and predict cooperative and competitive
behavior in evolving social networks.
To deal with overlapping communities we introduce a soft community detection and
outline its possible applications in single and multi-layer graphs. In particular, we
propose friend-recommendations in social networks, where new link recommendations
are made as intra- and inter-clique communities completion and recommendations are
prioritized according to topologically-based similarity measures (Liben-Nowel & Kleinberg,
2003) modified to include multiple-communities membership. We also show that the
proposed prediction rules based on soft community detection are in line with the network
evolution predicted by coupled dynamical systems. To test the proposed framework we
use a benchmark network (Zachary, 1977) and then apply developed methods for analysis
of multi-layers graphs built from real-world mobile datasets (Kiukkonen et al, 2010). The
presented results show that by combining information from multi-layer graphs we can
improve reliability measures of community detection and missing links predictions.
The chapter is organized as follows: in Section 2 we outline the dynamical formulation of
community detection that forms the basis for the rest of the paper. Topology detection using
coupled dynamical systems and its extensions to model a network evolution are described
in Section 3. Soft community detection for networks with overlapping communities and its
applications are addressed in Section 4, followed by combining multi-layer graphs in Section
5. Evaluation of the proposed methods in the benchmark network are presented in Section
6. Analysis of some real-world datesets collected during Nokia data collection campaign is
presented in Section 7, followed by conclusions in Section 8.
2. Community detection
2.1 Modularity maximization
Let's consider the clustering problem for an undirected graph G
N
nodes and E edges. Recently Newman et al (Girvan & Newman, 2002; 2004) introduced a new
measure for graph clustering„ named a modularity, which is defined as a number connections
within a group compared to the expected number of such connections in an equivalent null
model (e.g., in an equivalent random graph). In particular, the modularity Q of a partition
=(
V , E
)
with
|
V
| =
P
may be written as
i , j A ij P ij δ ( c i , c j ) ,
1
2 m
=
Q
(1)
where c i is the i -th community., A ij are elements of graph adjacency matrix; d i is the
i -th
node degree, d i = ∑ j A ij ; m is a total number of links m
= ∑ i d i /2; P ij is a probability that
nodes i and j in a null model are connected; if a random graph is taken as the null model, then
Search WWH ::




Custom Search