2

python + igraphを使用して、有向グラフで密なサブグラフを見つけるアルゴリズムを実装しています。メイン ループは、最初は同一である 2 つのサブグラフ S および T を維持し、他のグラフに対するこれらのノードの入次数 (または出次数) のカウントに従ってノード (およびインシデント エッジ) を削除します。私が抱えている問題は、igraph が頂点の番号を付け直すため、T からいくつかを削除すると、残りのノードが S の同じノードに対応しなくなることです。

これが重要なループの主要部分です。

def directed(S):
    T = S.copy()
    c = 2
    while(S.vcount() > 0 and T.vcount() > 0):
        if (S.vcount()/T.vcount() > c):
            AS = S.vs.select(lambda vertex: T.outdegree(vertex) < 1.01*E(S,T)/S.vcount())
            S.delete_vertices(AS)
        else:
            BT = T.vs.select(lambda vertex: S.indegree(vertex) < 1.01*E(S,T)/T.vcount())
            T.delete_vertices(BT)

これは、頂点 ID に対する頂点の削除の影響により機能しません。この問題の標準的な回避策はありますか?

4

1 に答える 1

3

name1つの可能性は、頂点属性の頂点に一意の名前を割り当てることです。これらは（頂点IDとは異なり）頂点が削除されてもそのまま保持され、indegreeまたはのような関数で頂点を参照するために使用できますoutdegree。例えば：

>>> g = Graph.Ring(4)
>>> g.vs["name"] = ["A", "B", "C", "D"]
>>> g.degree("C")
2
>>> g.delete_vertices(["B"])
>>> g.degree("C")
1

頂点を削除しBたため、頂点Cも新しいIDを取得しましたが、名前は同じであることに注意してください。

あなたの場合、select条件のある行はおそらく次のように書き直される可能性があります。

AS = S.vs.select(lambda vertex: T.outdegree(vertex["name"]) < 1.01 * E(S,T)/S.vcount())

もちろん、これは最初は頂点名がとで同じであることを前提としていSますT。

于 2012-08-24T21:47:23.457 に答える