Biology Reference
In-Depth Information
7.3.1.
The Critical Node Detection Problem
Given a graph
G
=(
V,E
),let
u
:
V
,where
u
ij
=1if nodes
i
and
j
are in the same component of
V
. Then the objective of the
CNDP
is to find a
subset
A
×
V
→{
0
,
1
}
k
, whose deletion results in the minimum
value of
u
ij
in the edge induced subgraph
G
(
V
⊆
V
of nodes such that
|
A
|≤
A
). This objective function
results in a minimum cohesion in the network, while also ensuring a minimum
difference in the sizes of the components. An integer programming formulation
of the
CNDP
has been formulated by Arulselvan et al. [2]
Let
u
be definedasaboveanddefine
v
:
V
\
as
v
i
:=
1, if node
i
is deleted in the optimal solution,
0,otherwise.
→{
0
,
1
}
(7.1)
Then the
CRITICAL NODE DETECTION PROBLEM
is given as
Minimize
i,j
(CNDP)
u
ij
(7.2)
∈
V
s.t.
u
ij
+
v
i
+
v
j
≥
1
,
∀
(
i,j
)
∈
E,
(7.3)
u
ij
+
u
jk
−
u
ki
≤
1
,
∀
(
i,j,k
)
∈
V,
(7.4)
u
ij
−u
jk
+
u
ki
≤
1
, ∀
(
i,j,k
)
∈ V,
(7.5)
−
u
ij
+
u
jk
+
u
ki
≤
1
,
∀
(
i,j,k
)
∈
V,
(7.6)
v
i
≤
k,
(7.7)
i
∈
V
u
ij
∈{
0
,
1
}
,
∀
i,j
∈
V,
(7.8)
v
i
∈{
0
,
1
}
,
∀
i
∈
V.
(7.9)
Constraints (7.3) ensure that if (
i,j
)
E
and nodes
i
and
j
are in separate compo-
nents, then one or both of them is deleted. The set of constraints (7.4-7.6) ensure
that if nodes
i
and
j
are in the same component and nodes
j
and
k
are in the same
component, then necessarily
i
and
k
belong to the same component. Finally, (7.7)
constrains the maximum number of nodes to be deleted. The
CNDP
was shown to
be
∈
NP
-hard [12] by a reduction of
MAXIMUM INDEPENDENT SET
to an instance
of the
CNDP
[3].
7.3.2.
Cardinality Constrained Problem
Given a graph
G
=(
V,E
),the
connectivity index
of a node is defined as the num-
ber of nodes reachable from that vertex (see Fig. 7.1 for examples). To constrain
Search WWH ::
Custom Search