### annotate env/lib/python3.9/site-packages/networkx/algorithms/approximation/clique.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """Functions for computing large cliques."""
shellac
parents:
diff changeset
2 import networkx as nx
shellac
parents:
diff changeset
3 from networkx.utils import not_implemented_for
shellac
parents:
diff changeset
4 from networkx.algorithms.approximation import ramsey
shellac
parents:
diff changeset
5
shellac
parents:
diff changeset
6 __all__ = ["clique_removal", "max_clique", "large_clique_size"]
shellac
parents:
diff changeset
7
shellac
parents:
diff changeset
8
shellac
parents:
diff changeset
9 def max_clique(G):
shellac
parents:
diff changeset
10 r"""Find the Maximum Clique
shellac
parents:
diff changeset
11
shellac
parents:
diff changeset
12 Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set
shellac
parents:
diff changeset
13 in the worst case.
shellac
parents:
diff changeset
14
shellac
parents:
diff changeset
15 Parameters
shellac
parents:
diff changeset
16 ----------
shellac
parents:
diff changeset
17 G : NetworkX graph
shellac
parents:
diff changeset
18 Undirected graph
shellac
parents:
diff changeset
19
shellac
parents:
diff changeset
20 Returns
shellac
parents:
diff changeset
21 -------
shellac
parents:
diff changeset
22 clique : set
shellac
parents:
diff changeset
23 The apx-maximum clique of the graph
shellac
parents:
diff changeset
24
shellac
parents:
diff changeset
25 Notes
shellac
parents:
diff changeset
26 ------
shellac
parents:
diff changeset
27 A clique in an undirected graph G = (V, E) is a subset of the vertex set
shellac
parents:
diff changeset
28 C \subseteq V such that for every two vertices in C there exists an edge
shellac
parents:
diff changeset
29 connecting the two. This is equivalent to saying that the subgraph
shellac
parents:
diff changeset
30 induced by C is complete (in some cases, the term clique may also refer
shellac
parents:
diff changeset
31 to the subgraph).
shellac
parents:
diff changeset
32
shellac
parents:
diff changeset
33 A maximum clique is a clique of the largest possible size in a given graph.
shellac
parents:
diff changeset
34 The clique number \omega(G) of a graph G is the number of
shellac
parents:
diff changeset
35 vertices in a maximum clique in G. The intersection number of
shellac
parents:
diff changeset
36 G is the smallest number of cliques that together cover all edges of G.
shellac
parents:
diff changeset
37
shellac
parents:
diff changeset
38 https://en.wikipedia.org/wiki/Maximum_clique
shellac
parents:
diff changeset
39
shellac
parents:
diff changeset
40 References
shellac
parents:
diff changeset
41 ----------
shellac
parents:
diff changeset
42 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
shellac
parents:
diff changeset
43 Approximating maximum independent sets by excluding subgraphs.
shellac
parents:
diff changeset
44 BIT Numerical Mathematics, 32(2), 180–196. Springer.
shellac
parents:
diff changeset
45 doi:10.1007/BF01994876
shellac
parents:
diff changeset
46 """
shellac
parents:
diff changeset
47 if G is None:
shellac
parents:
diff changeset
48 raise ValueError("Expected NetworkX graph!")
shellac
parents:
diff changeset
49
shellac
parents:
diff changeset
50 # finding the maximum clique in a graph is equivalent to finding
shellac
parents:
diff changeset
51 # the independent set in the complementary graph
shellac
parents:
diff changeset
52 cgraph = nx.complement(G)
shellac
parents:
diff changeset
53 iset, _ = clique_removal(cgraph)
shellac
parents:
diff changeset
54 return iset
shellac
parents:
diff changeset
55
shellac
parents:
diff changeset
56
shellac
parents:
diff changeset
57 def clique_removal(G):
shellac
parents:
diff changeset
58 r""" Repeatedly remove cliques from the graph.
shellac
parents:
diff changeset
59
shellac
parents:
diff changeset
60 Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique
shellac
parents:
diff changeset
61 and independent set. Returns the largest independent set found, along
shellac
parents:
diff changeset
62 with found maximal cliques.
shellac
parents:
diff changeset
63
shellac
parents:
diff changeset
64 Parameters
shellac
parents:
diff changeset
65 ----------
shellac
parents:
diff changeset
66 G : NetworkX graph
shellac
parents:
diff changeset
67 Undirected graph
shellac
parents:
diff changeset
68
shellac
parents:
diff changeset
69 Returns
shellac
parents:
diff changeset
70 -------
shellac
parents:
diff changeset
71 max_ind_cliques : (set, list) tuple
shellac
parents:
diff changeset
72 2-tuple of Maximal Independent Set and list of maximal cliques (sets).
shellac
parents:
diff changeset
73
shellac
parents:
diff changeset
74 References
shellac
parents:
diff changeset
75 ----------
shellac
parents:
diff changeset
76 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
shellac
parents:
diff changeset
77 Approximating maximum independent sets by excluding subgraphs.
shellac
parents:
diff changeset
78 BIT Numerical Mathematics, 32(2), 180–196. Springer.
shellac
parents:
diff changeset
79 """
shellac
parents:
diff changeset
80 graph = G.copy()
shellac
parents:
diff changeset
81 c_i, i_i = ramsey.ramsey_R2(graph)
shellac
parents:
diff changeset
82 cliques = [c_i]
shellac
parents:
diff changeset
83 isets = [i_i]
shellac
parents:
diff changeset
84 while graph:
shellac
parents:
diff changeset
85 graph.remove_nodes_from(c_i)
shellac
parents:
diff changeset
86 c_i, i_i = ramsey.ramsey_R2(graph)
shellac
parents:
diff changeset
87 if c_i:
shellac
parents:
diff changeset
88 cliques.append(c_i)
shellac
parents:
diff changeset
89 if i_i:
shellac
parents:
diff changeset
90 isets.append(i_i)
shellac
parents:
diff changeset
91 # Determine the largest independent set as measured by cardinality.
shellac
parents:
diff changeset
92 maxiset = max(isets, key=len)
shellac
parents:
diff changeset
93 return maxiset, cliques
shellac
parents:
diff changeset
94
shellac
parents:
diff changeset
95
shellac
parents:
diff changeset
96 @not_implemented_for("directed")
shellac
parents:
diff changeset
97 @not_implemented_for("multigraph")
shellac
parents:
diff changeset
98 def large_clique_size(G):
shellac
parents:
diff changeset
99 """Find the size of a large clique in a graph.
shellac
parents:
diff changeset
100
shellac
parents:
diff changeset
101 A *clique* is a subset of nodes in which each pair of nodes is
shellac
parents:
diff changeset
102 adjacent. This function is a heuristic for finding the size of a
shellac
parents:
diff changeset
103 large clique in the graph.
shellac
parents:
diff changeset
104
shellac
parents:
diff changeset
105 Parameters
shellac
parents:
diff changeset
106 ----------
shellac
parents:
diff changeset
107 G : NetworkX graph
shellac
parents:
diff changeset
108
shellac
parents:
diff changeset
109 Returns
shellac
parents:
diff changeset
110 -------
shellac
parents:
diff changeset
111 int
shellac
parents:
diff changeset
112 The size of a large clique in the graph.
shellac
parents:
diff changeset
113
shellac
parents:
diff changeset
114 Notes
shellac
parents:
diff changeset
115 -----
shellac
parents:
diff changeset
116 This implementation is from [1]_. Its worst case time complexity is
shellac
parents:
diff changeset
117 :math:O(n d^2), where *n* is the number of nodes in the graph and
shellac
parents:
diff changeset
118 *d* is the maximum degree.
shellac
parents:
diff changeset
119
shellac
parents:
diff changeset
120 This function is a heuristic, which means it may work well in
shellac
parents:
diff changeset
121 practice, but there is no rigorous mathematical guarantee on the
shellac
parents:
diff changeset
122 ratio between the returned number and the actual largest clique size
shellac
parents:
diff changeset
123 in the graph.
shellac
parents:
diff changeset
124
shellac
parents:
diff changeset
125 References
shellac
parents:
diff changeset
126 ----------
shellac
parents:
diff changeset
127 .. [1] Pattabiraman, Bharath, et al.
shellac
parents:
diff changeset
128 "Fast Algorithms for the Maximum Clique Problem on Massive Graphs
shellac
parents:
diff changeset
129 with Applications to Overlapping Community Detection."
shellac
parents:
diff changeset
130 *Internet Mathematics* 11.4-5 (2015): 421--448.
shellac
parents:
diff changeset
131 <https://doi.org/10.1080/15427951.2014.986778>
shellac
parents:
diff changeset
132
shellac
parents:
diff changeset
shellac
parents:
diff changeset
134 --------
shellac
parents:
diff changeset
135
shellac
parents:
diff changeset
136 :func:networkx.algorithms.approximation.clique.max_clique
shellac
parents:
diff changeset
137 A function that returns an approximate maximum clique with a
shellac
parents:
diff changeset
138 guarantee on the approximation ratio.
shellac
parents:
diff changeset
139
shellac
parents:
diff changeset
140 :mod:networkx.algorithms.clique
shellac
parents:
diff changeset
141 Functions for finding the exact maximum clique in a graph.
shellac
parents:
diff changeset
142
shellac
parents:
diff changeset
143 """
shellac
parents:
diff changeset
144 degrees = G.degree
shellac
parents:
diff changeset
145
shellac
parents:
diff changeset
146 def _clique_heuristic(G, U, size, best_size):
shellac
parents:
diff changeset
147 if not U:
shellac
parents:
diff changeset
148 return max(best_size, size)
shellac
parents:
diff changeset
149 u = max(U, key=degrees)
shellac
parents:
diff changeset
150 U.remove(u)
shellac
parents:
diff changeset
151 N_prime = {v for v in G[u] if degrees[v] >= best_size}
shellac
parents:
diff changeset
152 return _clique_heuristic(G, U & N_prime, size + 1, best_size)
shellac
parents:
diff changeset
153
shellac
parents:
diff changeset
154 best_size = 0
shellac
parents:
diff changeset
155 nodes = (u for u in G if degrees[u] >= best_size)
shellac
parents:
diff changeset
156 for u in nodes:
shellac
parents:
diff changeset
157 neighbors = {v for v in G[u] if degrees[v] >= best_size}