Image Processing Reference
In-Depth Information
• each new link creates at least one new clique (the FoF concept);
• complete cliques within the same community (intra-cliques) using the FoF concept;
• complete cliques towards to the fully-connected own community if there is no FoF links;
• complete inter-cliques (where nodes belong to different communities);
• prioritize intra-clique and inter-clique links completion according to some measure based
on multi-membership.
To assign priorities we introduce several similarity measures outlined below. We will show in
next sections that these rules are well in line with link predictions made by coupled dynamical
systems described in Section 3.
Modified topology-based predictors
Let'a define sets of neighbors of node k , which are inside and outside of community c i
as
Γ i (
)= { Γ(
)
c i }
Γ \ i (
)= { Γ(
)
c i }
, respectively. This allows us to
introduce a set of similarity measures by modifying topology-based base-line predictors
listed in (Liben-Nowel & Kleinberg, 2003) to take into account the multiple-membership in
overlapping communities.
As an example, for the intra-clique completion we may associate a quality of missing link
prediction (or recommendation) between nodes k and n within c i community by modifying
the base-line predictor scores as follows:
- Preferential attachment: S ( i , i )
P
k
k
and
k
k
/
(
k , n
)= | Γ i
(
k
) |·| Γ i
(
n
) |
;
A
- Jaccards score: S ( i , i )
J
C (
k , n
)= | Γ i (
k
) Γ i (
n
) |
/
| Γ i (
k
) Γ i (
n
) |
;
-Adamic/Adarscore: S ( i , i )
) | ) 1 ;
AA (
)=∑ z Γ i ( k ) Γ i ( n ) (
| Γ(
k , n
log
z
- Katz score (intra-community):
I
l = 1 β
S ( i , i )
l
) ( l ) | =
A ( i ) ) 1
KC (
k , n
)=
| path (
k , n
(
I
β
,
(
k , n
)
) ( l ) |
| path i (
where
k , n
is number of all paths of length- l from k to n within c i ; I is the identity
matrix, A ( i )
is the (weighted) adjacency matrix of community c i ,
β
is a dumping parameter,
0
1.
Additionally to the base-line predictors above,
< β <
1, such that
ij β
A ij <
we also use a community connectivity
measure, S ( i , i )
, which characterizes a convergence speed of opinions to
consensus within a community c i when a link between nodes k and n is added inside the
community; here
CC (
k , n
) σ 2
(
L i
)
is the 2nd smallest eigenvalue of the graph Laplacian L i of community
c i (or the normalized Laplacian for weighted graphs, based on (17)).
The measures above consider communities as disjoint sets and may be used as the 1st order
approximation for link predictions in overlapping communities. To take into account both
intra- and inter-community links we use multi-community membership for nodes, g i (
σ 2 (
L
)
k
)
.In
general, for nodes k
c i and n
c j , the inter-community relations may be asymmetric,
g j (
) =
g i (
)
. In the case of undirected graphs we may use averaging and modify the
base-line predictors S
k
n
(
)
k , n
as
g j (
k
)+
g i (
n
)
S ( i , j ) (
)=
(
)
k , n
S
k , n
.
(30)
2 m
Search WWH ::




Custom Search