Statistics
| Branch: | Revision:

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

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2011-2019 by ``` ```# Nicholas Mancuso ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# Copyright 2016-2019 NetworkX developers. ``` ```# NetworkX is distributed under a BSD license ``` ```# ``` ```# Authors: Nicholas Mancuso (nick.mancuso@gmail.com) ``` ```# Jeffery Finkelstein ``` ```# Dan Schult ``` ```"""Functions for computing large cliques.""" ``` ```from operator import itemgetter ``` ```import networkx as nx ``` ```from networkx.utils import not_implemented_for ``` ```from networkx.algorithms.approximation import ramsey ``` ```__all__ = ["clique_removal", "max_clique", "large_clique_size"] ``` ```def max_clique(G): ``` ``` r"""Find the Maximum Clique ``` ``` ``` ``` Finds the \$O(|V|/(log|V|)^2)\$ apx of maximum clique/independent set ``` ``` in the worst case. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` Undirected graph ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` clique : set ``` ``` The apx-maximum clique of the graph ``` ``` ``` ``` Notes ``` ``` ------ ``` ``` A clique in an undirected graph G = (V, E) is a subset of the vertex set ``` ``` `C \subseteq V` such that for every two vertices in C there exists an edge ``` ``` connecting the two. This is equivalent to saying that the subgraph ``` ``` induced by C is complete (in some cases, the term clique may also refer ``` ``` to the subgraph). ``` ``` ``` ``` A maximum clique is a clique of the largest possible size in a given graph. ``` ``` The clique number `\omega(G)` of a graph G is the number of ``` ``` vertices in a maximum clique in G. The intersection number of ``` ``` G is the smallest number of cliques that together cover all edges of G. ``` ``` ``` ``` https://en.wikipedia.org/wiki/Maximum_clique ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Boppana, R., & Halldórsson, M. M. (1992). ``` ``` Approximating maximum independent sets by excluding subgraphs. ``` ``` BIT Numerical Mathematics, 32(2), 180–196. Springer. ``` ``` doi:10.1007/BF01994876 ``` ``` """ ``` ``` if G is None: ``` ``` raise ValueError("Expected NetworkX graph!") ``` ``` # finding the maximum clique in a graph is equivalent to finding ``` ``` # the independent set in the complementary graph ``` ``` cgraph = nx.complement(G) ``` ``` iset, _ = clique_removal(cgraph) ``` ``` return iset ``` ```def clique_removal(G): ``` ``` r""" Repeatedly remove cliques from the graph. ``` ``` ``` ``` Results in a \$O(|V|/(\log |V|)^2)\$ approximation of maximum clique ``` ``` and independent set. Returns the largest independent set found, along ``` ``` with found maximal cliques. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` Undirected graph ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` max_ind_cliques : (set, list) tuple ``` ``` 2-tuple of Maximal Independent Set and list of maximal cliques (sets). ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Boppana, R., & Halldórsson, M. M. (1992). ``` ``` Approximating maximum independent sets by excluding subgraphs. ``` ``` BIT Numerical Mathematics, 32(2), 180–196. Springer. ``` ``` """ ``` ``` graph = G.copy() ``` ``` c_i, i_i = ramsey.ramsey_R2(graph) ``` ``` cliques = [c_i] ``` ``` isets = [i_i] ``` ``` while graph: ``` ``` graph.remove_nodes_from(c_i) ``` ``` c_i, i_i = ramsey.ramsey_R2(graph) ``` ``` if c_i: ``` ``` cliques.append(c_i) ``` ``` if i_i: ``` ``` isets.append(i_i) ``` ``` # Determine the largest independent set as measured by cardinality. ``` ``` maxiset = max(isets, key=len) ``` ``` return maxiset, cliques ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def large_clique_size(G): ``` ``` """Find the size of a large clique in a graph. ``` ``` ``` ``` A *clique* is a subset of nodes in which each pair of nodes is ``` ``` adjacent. This function is a heuristic for finding the size of a ``` ``` large clique in the graph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` int ``` ``` The size of a large clique in the graph. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` This implementation is from _. Its worst case time complexity is ``` ``` :math:`O(n d^2)`, where *n* is the number of nodes in the graph and ``` ``` *d* is the maximum degree. ``` ``` ``` ``` This function is a heuristic, which means it may work well in ``` ``` practice, but there is no rigorous mathematical guarantee on the ``` ``` ratio between the returned number and the actual largest clique size ``` ``` in the graph. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Pattabiraman, Bharath, et al. ``` ``` "Fast Algorithms for the Maximum Clique Problem on Massive Graphs ``` ``` with Applications to Overlapping Community Detection." ``` ``` *Internet Mathematics* 11.4-5 (2015): 421--448. ``` ``` ``` ``` ``` ``` See also ``` ``` -------- ``` ``` ``` ``` :func:`networkx.algorithms.approximation.clique.max_clique` ``` ``` A function that returns an approximate maximum clique with a ``` ``` guarantee on the approximation ratio. ``` ``` ``` ``` :mod:`networkx.algorithms.clique` ``` ``` Functions for finding the exact maximum clique in a graph. ``` ``` ``` ``` """ ``` ``` degrees = G.degree ``` ``` def _clique_heuristic(G, U, size, best_size): ``` ``` if not U: ``` ``` return max(best_size, size) ``` ``` u = max(U, key=degrees) ``` ``` U.remove(u) ``` ``` N_prime = {v for v in G[u] if degrees[v] >= best_size} ``` ``` return _clique_heuristic(G, U & N_prime, size + 1, best_size) ``` ``` best_size = 0 ``` ``` nodes = (u for u in G if degrees[u] >= best_size) ``` ``` for u in nodes: ``` ``` neighbors = {v for v in G[u] if degrees[v] >= best_size} ``` ``` best_size = _clique_heuristic(G, neighbors, 1, best_size) ``` ``` return best_size ```