Biology Reference
In-Depth Information
maximum clique problem is to find a clique
C
with maximum cardinality (size)
|
. The maximum clique problem can be represented in many equivalent formu-
lations (e.g., an integer programming problem, a continuous global optimization
problem, and an indefinite quadratic programming). In this paper, we represent it
in a simple integer programming form given by
C
|
max
x
i
(14.6)
E
s.t.
x
i
+
x
j
≤
1
,
where (
i,j
)
/
∈
(14.7)
x
i
∈{
0
,
1
}
,
(14.8)
where
x
i
is binary variable indicating if electrode
i
is a member of the maxi-
mum clique. In finding the maximum clique in the brain networks, we applied
the Carraghan-Pardalos maximum clique algorithm [6].
A pseudocode for this
algorithm is provided in Fig. 14.6.
algorithm:
maximum clique
begin
sort all nodes based on vertex ordering
LIST = ordered nodes
cbc = 0 current best clique size
depth = 0 current depth level
enter-next-depth(LIST,depth)
end
procedure:
enter-next-depth(LIST,depth)
begin
1
m = the number of nodes in the LIST
2
depth=depth+1
3
for
a node in position i in the LIST
4
if
depth+(m-i)
≤
cbc
then
5
return prune the search
6
else
7
mark node i
8
if
no adjacent node
then
9
cbc=depth (maximum clique found)
10
else
11
enter to next depth (adjacent node of i, depth)
12
end
13
end
14
unmark node i
15
if
depth=1
16
delete node i from LIST
17
end
18
end
end
Fig. 14.6.
The maximum clique algorithm
Search WWH ::
Custom Search