Information Technology Reference
In-Depth Information
A clique is simply a 1-plex as a special case. Since finding maximum
n
-plexes
is
-hard for all natural numbers
n>
0, any approach based on the
n
-plex
would have some intrinsic limitation on applicability to large-scale networks.
NP
The
k
-Core Extraction Algorithm
14.2.6
For a given core order
k
, we describe a basic algorithm for extracting a
k
-core
from a network
G
=(
V
G
,E
G
). The basic idea is to recursively eliminate the
set of nodes that do not satisfy the
k
-core condition. The basic procedure for
calculating (
V
C
(
k
)
,E
C
(
k
)
)=
cor
k
(
V
G
,E
G
) is described as follows:
1.
Initialize
V
C
(
k
)
=
V
G
,
E
C
(
k
)
=
E
G
;
2.
Compute
T
=
A
{
i
:
|
F
C
(
k
)
(
i
)
|
<k
−
1
}
;
3.
If
T
=
, output (
V
C
(
k
)
,E
C
(
k
)
)andterminate;
4.
Set
V
C
(
k
)
=
V
C
(
k
)
−
∅
T
,
E
C
(
k
)
=
E
C
(
k
)
−{
e
m
:
e
m
∩
T
=
∅}
,and
return to
2
.
Here
T
denotes a set of nodes for elimination under the
k
-core condition.
The algorithm above extracts
k
-core for a fixed
k
. However, it is not realistic
to assume that we know an appropriate core order
k
in advance. Fortunately,
the maximum core order is bounded to max
i
{
F
G
(
i
)
}
, and thus by making use
of the property
C
(
k
+1)
⊂
C
(
k
), we can iteratively compute
k
-core for every
k
quite eciently as follows:
1.
Initialize
V
C
(1)
=
V
G
,
E
C
(1)
=
E
G
,andset
k
=2;
2.
Compute (
V
C
(
k
)
,E
D
(
k
)
)=
core
k
A
(
V
C
(
k−
1)
,E
C
(
k−
1)
);
, then terminate;
4.
Set
k
=
k
+ 1, and return to
2
.
Note that extracting a
k
-core at
k
= 2 is equivalent to eliminating a set of
isolated nodes. Hereafter this method is referred to as the
k
-core method.
3.
If
V
C
(
k
)
=
∅
14.2.7
The
k
-Dense Extraction Algorithm
As mentioned earlier, by using the fact that
D
(
k
)
C
(
k
), we can utilize the
k
-core method for extracting a
k
-dense. The basic procedure for calculating
(
V
D
(
k
)
,E
D
(
k
)
)=
⊂
dense
k
(
V
G
,E
G
) is described as follows:
1.
Initialize
V
D
(
k
)
=
V
G
,
E
D
(
k
)
=
E
G
;
2.
Compute (
V
D
(
k
)
,E
D
(
k
)
)=
A
core
k
A
(
V
D
(
k
)
,E
D
(
k
)
)
3.
Compute
L
=
{
e
m
:
|
F
D
(
k
)
(
e
m
)
|
<k
−
2
}
;
4.
If
L
=
, output (
V
D
(
k
)
,E
D
(
k
)
)andterminate;
5.
Set
E
D
(
k
)
=
E
D
(
k
)
−
∅
L
and return to
2
.
Here
L
denotes a set of links for elimination under the
k
-dense condition.
By using the property
D
(
k
+1)
⊂
D
(
k
), we can iteratively compute
k
-dense
for every
k
as follows:
