large_clique_size

large_clique_size(G)

寻找图中的一个大型团的大小。

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

Parameters:

GNetworkX 图

Returns:

k: 整数

图中一个大型团的大小。

Raises:

NetworkXNotImplemented

如果图是有向的或是一个多重图。

See also

networkx.algorithms.approximation.clique.max_clique()

返回具有近似比率保证的近似最大团的函数。

networkx.algorithms.clique

用于在图中寻找精确最大团的功能。

Notes

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

此函数是一种启发式方法，这意味着它在实践中可能表现良好，但对于返回的数字与图中实际最大团大小之间的比率，没有严格的数学保证。

References

[1]

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

Examples

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