Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / clique.py @ 5cef0f13

History | View | Annotate | Download (5.28 KB)

1
# -*- coding: utf-8 -*-
2
#   Copyright (C) 2011-2019 by
3
#   Nicholas Mancuso <nick.mancuso@gmail.com>
4
#   All rights reserved.
5
#   BSD license.
6
#   Copyright 2016-2019 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|/(log|V|)^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 apx-maximum 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
        2-tuple 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.4-5 (2015): 421--448.
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