知识卡片

延伸参考卡 · 6255.a

团枚举要区分输出与筛选

理解等级:中级

NetworkX的find_cliques枚举无向图的极大团,书中先全部转成列表,再按长度找最大者,所以num_cliques数的是极大团而非所有子团。当前官方文档明确输出数量最坏可随节点数指数增长;一次性列表还会存下全部输出。枚举、找最大值与判定是否存在给定大小的团是不同任务,不把“NP完全”简化为每次输入都必耗指数时间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      find_cliques(http://1.usa.gov/1a1lKzk)方法,该方法提供了这个难题的完整实现。要注意,如果图的大小超过合理的范围,那么运行该方法会花费很长时间(上面提到的指数级运行时间)。示例2-13和2-14显示了如何使用Facebook数据构建一个相互好友关系图并且使用NetworkX分析图中的团。你可以在终端输入pip instal

    参考来源

    - 位置:《社交网站的数据挖掘与分析(原书第2版)》第2章《2.3.2 查看好友关系》(spine72;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0061.html;u038-ch02-028)。 - 结论依据:原文在“find_cliques”附近的定义、例子或代码支撑本卡核心说明:NetworkX的find_cliques枚举无向图的极大团,书中先全部转成列表,再按长度找最大者,所以num_cliques数的是极大团而非所有子团。边界按已读前提解释;示例未执行。 - 原始内容:find_cliques(http://1.usa.gov/1a1lKzk)方法,该方法提供了这个难题的完整实现。要注意,如果图的大小超过合理的范围,那么运行该方法会花费很长时间(上面提到的指数级运行时间)。示例2-13和2-14显示了如何使用Facebook数据构建一个相互好友关系图并且使用NetworkX分析图中的团。你可以在终端输入pip instal