Database Reference
In-Depth Information
where
(
v
) is the
structure
of node
v
and is defined as
G
G
ð
v
Þ¼f
w
2
V
jð
v
;
w
Þ2
E
g[f
v
g
(5.2)
Definition 3.
The
-neighborhood of a node is the subset of its structure containing
only those nodes that are at least
e
e
-similar with the node; in math notation:
N
e
ð
v
Þ¼f
w
2
G
ð
v
Þ sð
j
v
;
w
Þe
g
(5.3)
Definition 4.
A vertex v is called a (
m
,
e
)-core if its
e
-neighborhood contains at least
m
vertices; formally:
CORE
m;e
ð
v
Þ,
j
N
e
ð
v
Þ
j m
(5.4)
Definition 5.
A node is directly structure reachable from a (
m
,
e
)-core if it is at least
e
-similar to it: DirReach
m
,
e
(v
,
w)
,
CORE
m
,
e
(
v
)
∧
w
∈
N
e
(
v
).
m
e
)-cores of a network have been identified, it is possible to start
attaching adjacent nodes to them provided that they are reachable through a chain of
nodes which are directly structure reachable from each other. We call the resulting
set of nodes as a
community seed set
. An example of computing structural similarity
values for the edges of a network and then identifying the underlying (
Once the (
,
)-cores,
hubs, and outliers of the network is illustrated in Fig.
5.2
. This technique for
collecting community seed sets is computationally efficient since its complexity
is
O
m
,
e
for a network of
n
edges and average degree
k
. Computing the structural
similarity value for every edge of the network introduces an additional
O
ðk
n
Þ
ðk
m
Þ
complexity in the community detection scheme.
Fig. 5.2 Example of community structure in an artificial network. Nodes are labeled with
successive numbers and edges are labeled with the structural similarity value between the nodes
that they connect. Nodes 1 and 10 are (
m
,
e
)-cores with
m ¼
5 and
e ¼
0.65. Nodes 2-6 are
structure reachable from node 1 and nodes 9, 11-15 are structure reachable from node 10. Thus,
two community seed sets have been identified: the first consisting of nodes 1-6 and the second
consisting of nodes 9-15
Search WWH ::
Custom Search