large_clique_size#

large_clique_size(G)[source]#

查找图中大型团的大小。

团是节点的一个子集，其中每对节点都是相邻的。此函数是一个启发式算法，用于查找图中大型团的大小。

参数:

GNetworkX 图

返回:

k: 整数

图中大型团的大小。

抛出异常:

NetworkXNotImplemented

如果图是有向图或多重图。

另请参阅

networkx.algorithms.approximation.clique.max_clique()

一个返回近似最大团的函数，并附带近似比保证。

networkx.algorithms.clique

用于查找图中精确最大团的函数。

注意

此实现来自 [1]。其最坏情况时间复杂度为 $O(n{d}^2)$，其中 n 是图中的节点数，d 是最大度。

此函数是一个启发式算法，这意味着它在实践中可能效果不错，但对于返回的数值与图中实际最大团大小之间的比率没有严格的数学保证。

参考文献

[1]

Pattabiraman, Bharath, et al. “大规模图上的最大团问题快速算法及其在重叠社区检测中的应用。” Internet Mathematics 11.4-5 (2015): 421–448. <https://doi.org/10.1080/15427951.2014.986778>

示例

>>> G = nx.path_graph(10)
>>> nx.approximation.large_clique_size(G)
2