Image Processing Reference
In-Depth Information
For example, modified Jaccards and Katz scores which take into account multi-communities
membership are defined as
g
j
(
)+
g
i
(
)
k
n
|
Γ
(
k
)
∩
Γ
(
n
)
|
S
(
i
,
j
)
J
(
k
,
n
)=
,
(31)
C
2
m
|
Γ
(
k
)
∪
Γ
(
n
)
|
I
g
j
(
)+
g
i
(
)
k
n
S
(
i
,
j
)
A
(
C
n
,
k
)
)
−
1
KC
(
k
,
n
)=
(
I
−
β
−
,
(32)
2
m
(
k
,
n
)
c
j
;
A
(
C
n
,
k
)
where
k
∈
c
i
,
n
∈
is an adjacency matrix formed by all communities relevant to
nodes
n
and
k
.
Recommendations also may be made in the probabilistic way, e.g., to be picked up from
distributions formed by modified prediction scores.
5. Multi-layer graphs
In analysis of multi-layer graphs we assume that different network layers capture different
modalities of the same underlying phenomena. For example, in case of mobile networks
the social relations are partly reflected in different interaction layers, such as phone and
SMS communications recorded in call-logs, people "closeness" extracted from the bluetooth
(BT) and WLAN proximity, common GPS locations and traveling patterns and etc. It may
be expected that a proper merging of data encoded in multi-graph layers can improve the
classification accuracy.
One approach to analyze multi-layer graphs is first to merge graphs according to some
rules and then extract communities from the combined graph. The layers may be combined
directly or using some functions defined on the graphs. For example, multiple graphs may
be aggregated in spectral domain using a joint block-matrix factorization or a regularization
framework (Dong et al, 2011). Another method is to extract spectral structural properties from
each layer separately and then to find a common presentation shared by all layers (Tang et all,
2009).
In this paper we consider methods of combining graphs based on modularity maximization
A
ij
d
i
d
j
2
m
1
2
m
i
,
j
max
Q
=
max
c
i
,
c
j
−
δ
(
c
j
,
c
j
)
.
(33)
d
i
d
j
2
m
. Then the modularity in
Let's define a modularity matrix
M
with elements
M
ij
=
A
ij
−
(33) may be presented as
2
m
Tr
G
T
G
dd
T
2
m
)
1
1
2
m
Tr
G
T
MG
Q
=
(
A
−
=
(
)
,
(34)
where columns of
N
×
N
c
matrix
G
describes community memberships for nodes,
g
j
(
i
)=
∈{
}
,
g
ij
=
1ifthe
i
-th node belongs to the community
c
j
;
N
c
is a number of
communities;
d
is a vector formed by degrees of nodes,
d
g
ij
0, 1
T
.
=(
d
1
,
···
,
d
N
)
G
=
{
G
1
,
G
2
,...,
G
L
}
A
=
Let's consider a multi-layer graph
with adjacency matrices
{
A
1
,
A
2
,...,
A
L
}
,where
L
is a number of layers.
Before combining.
the graphs are to be
normalized.
In case of modularity maximization (33) it is natural to normalize each layer
