networkx笔记

    xiaoxiao2026-05-22  6

    现在的任务是在一个结点比较多(二十五万条边)的有向图中找出(n个结点相互连通的圈子) 对于连通的定义(是强连通or弱连通还没有确立)

    尝试用cliques(派系)

    图论:一个由至少三个点构成的最大完备子图(所有节点均存在直接联系)

    极大团(maximal clique):再也不存在一个点,与该团的的任意顶点之间存在一条边。

    团数(clique number): 一个图的极大团的size。

    团的大小(size):一个团中包含的顶点数。 size=k的团,成为 k-团(k-clique)

    如果两个k-clique之间存在k-1个公共结点,则称这两个clique是相邻的。

    在nx.make_max_clique_graph(G)时卡死。终止时报MemoryError,应该是内存不够。 这条指令把最大的派系当做结点,如果最大的派系之间有相同的结点就判定代表他们的结点是联通的。 文档关于cliques的几条指令暂时对问题没有帮助,而且大多是针对无向图的…

    尝试用components(分量)

    强连通分量:有向图中每两个顶点都至少存在一条路径(感觉像是强连通圈子,但是实际中这种圈子太少了) max(nx.strongly_connected_component_subgraphs(G),key=len)将最大的强连通分量作为有向子图返回…但是画出来的图明显不是强连通分量。

    尝试用circle

    nx.find_circle(G,orientation=’ignore’) 最后画出来的比较符合需求!

    nx.enumerate_all_cliques(G)

    返回size从1到maxdegree-1的团,判断size大小可选出制定大小的团,但是超大网络怎么办?

    ?分布式集群?

    参考资料: ①复杂网络社区 http://blog.csdn.net/a_step_further/article/details/51176977

    ②图论 极大团 http://blog.sciencenet.cn/blog-1893836-836769.html

    转载请注明原文地址: https://ju.6miu.com/read-1309958.html
    最新回复(0)