ioftools / networkxMiCe / networkxmaster / networkx / algorithms / approximation / clique.py @ 5cef0f13
History  View  Annotate  Download (5.28 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20112019 by

3 
# Nicholas Mancuso <nick.mancuso@gmail.com>

4 
# All rights reserved.

5 
# BSD license.

6 
# Copyright 20162019 NetworkX developers.

7 
# NetworkX is distributed under a BSD license

8 
#

9 
# Authors: Nicholas Mancuso (nick.mancuso@gmail.com)

10 
# Jeffery Finkelstein <jeffrey.finkelstein@gmail.com>

11 
# Dan Schult <dschult@colgate.edu>

12 
"""Functions for computing large cliques."""

13 
from operator import itemgetter 
14  
15 
import networkx as nx 
16 
from networkx.utils import not_implemented_for 
17 
from networkx.algorithms.approximation import ramsey 
18  
19 
__all__ = ["clique_removal", "max_clique", "large_clique_size"] 
20  
21  
22 
def max_clique(G): 
23 
r"""Find the Maximum Clique

24 

25 
Finds the $O(V/(logV)^2)$ apx of maximum clique/independent set

26 
in the worst case.

27 

28 
Parameters

29 


30 
G : NetworkX graph

31 
Undirected graph

32 

33 
Returns

34 


35 
clique : set

36 
The apxmaximum clique of the graph

37 

38 
Notes

39 


40 
A clique in an undirected graph G = (V, E) is a subset of the vertex set

41 
`C \subseteq V` such that for every two vertices in C there exists an edge

42 
connecting the two. This is equivalent to saying that the subgraph

43 
induced by C is complete (in some cases, the term clique may also refer

44 
to the subgraph).

45 

46 
A maximum clique is a clique of the largest possible size in a given graph.

47 
The clique number `\omega(G)` of a graph G is the number of

48 
vertices in a maximum clique in G. The intersection number of

49 
G is the smallest number of cliques that together cover all edges of G.

50 

51 
https://en.wikipedia.org/wiki/Maximum_clique

52 

53 
References

54 


55 
.. [1] Boppana, R., & Halldórsson, M. M. (1992).

56 
Approximating maximum independent sets by excluding subgraphs.

57 
BIT Numerical Mathematics, 32(2), 180–196. Springer.

58 
doi:10.1007/BF01994876

59 
"""

60 
if G is None: 
61 
raise ValueError("Expected NetworkX graph!") 
62  
63 
# finding the maximum clique in a graph is equivalent to finding

64 
# the independent set in the complementary graph

65 
cgraph = nx.complement(G) 
66 
iset, _ = clique_removal(cgraph) 
67 
return iset

68  
69  
70 
def clique_removal(G): 
71 
r""" Repeatedly remove cliques from the graph.

72 

73 
Results in a $O(V/(\log V)^2)$ approximation of maximum clique

74 
and independent set. Returns the largest independent set found, along

75 
with found maximal cliques.

76 

77 
Parameters

78 


79 
G : NetworkX graph

80 
Undirected graph

81 

82 
Returns

83 


84 
max_ind_cliques : (set, list) tuple

85 
2tuple of Maximal Independent Set and list of maximal cliques (sets).

86 

87 
References

88 


89 
.. [1] Boppana, R., & Halldórsson, M. M. (1992).

90 
Approximating maximum independent sets by excluding subgraphs.

91 
BIT Numerical Mathematics, 32(2), 180–196. Springer.

92 
"""

93 
graph = G.copy() 
94 
c_i, i_i = ramsey.ramsey_R2(graph) 
95 
cliques = [c_i] 
96 
isets = [i_i] 
97 
while graph:

98 
graph.remove_nodes_from(c_i) 
99 
c_i, i_i = ramsey.ramsey_R2(graph) 
100 
if c_i:

101 
cliques.append(c_i) 
102 
if i_i:

103 
isets.append(i_i) 
104 
# Determine the largest independent set as measured by cardinality.

105 
maxiset = max(isets, key=len) 
106 
return maxiset, cliques

107  
108  
109 
@not_implemented_for('directed') 
110 
@not_implemented_for('multigraph') 
111 
def large_clique_size(G): 
112 
"""Find the size of a large clique in a graph.

113 

114 
A *clique* is a subset of nodes in which each pair of nodes is

115 
adjacent. This function is a heuristic for finding the size of a

116 
large clique in the graph.

117 

118 
Parameters

119 


120 
G : NetworkX graph

121 

122 
Returns

123 


124 
int

125 
The size of a large clique in the graph.

126 

127 
Notes

128 


129 
This implementation is from [1]_. Its worst case time complexity is

130 
:math:`O(n d^2)`, where *n* is the number of nodes in the graph and

131 
*d* is the maximum degree.

132 

133 
This function is a heuristic, which means it may work well in

134 
practice, but there is no rigorous mathematical guarantee on the

135 
ratio between the returned number and the actual largest clique size

136 
in the graph.

137 

138 
References

139 


140 
.. [1] Pattabiraman, Bharath, et al.

141 
"Fast Algorithms for the Maximum Clique Problem on Massive Graphs

142 
with Applications to Overlapping Community Detection."

143 
*Internet Mathematics* 11.45 (2015): 421448.

144 
<https://doi.org/10.1080/15427951.2014.986778>

145 

146 
See also

147 


148 

149 
:func:`networkx.algorithms.approximation.clique.max_clique`

150 
A function that returns an approximate maximum clique with a

151 
guarantee on the approximation ratio.

152 

153 
:mod:`networkx.algorithms.clique`

154 
Functions for finding the exact maximum clique in a graph.

155 

156 
"""

157 
degrees = G.degree 
158  
159 
def _clique_heuristic(G, U, size, best_size): 
160 
if not U: 
161 
return max(best_size, size) 
162 
u = max(U, key=degrees)

163 
U.remove(u) 
164 
N_prime = {v for v in G[u] if degrees[v] >= best_size} 
165 
return _clique_heuristic(G, U & N_prime, size + 1, best_size) 
166  
167 
best_size = 0

168 
nodes = (u for u in G if degrees[u] >= best_size) 
169 
for u in nodes: 
170 
neighbors = {v for v in G[u] if degrees[v] >= best_size} 
171 
best_size = _clique_heuristic(G, neighbors, 1, best_size)

172 
return best_size
