python - networkxのルールで不適切なノードを見つけますか?

Question

全て、

以下のサンプル「ツリー状」グラフを検討してください。

垂直方向には、ノード「0」ベースのレベル階層構造です。水平方向には、レベル 1 から始まるグループベースの構造です。グループとは、1 つのルートノードから継承されたノードを意味します。

    '''                         
                              +---+       
                              | 0 |                                    Level 0
                              +---+       
                                |
                 +--------------+---------------+         
                 |              |               |           
               +---+          +---+           +---+      
               | 1 |          | 2 |           | 3 |                    Level 1      
               +---+          +---+           +---+      
     +-----+----+        +-----+-----+        +|---+-----+            
     |     |     |        |     |     |        |    |     |           
   +---+ +---+ +---+    +---+ +---+ +---+   +---+ +---+ +---+  
   |11 | |12 | |13 |    |21 | |22 | |23 |   |31 | |32 | |33 |          Level 2 
   +---+ +---+ +---+    +---+ +---+ +---+   +---+ +---+ +---+  
     |     |   / |    /   |      |            |                 
     |     | /   | /      |      |            |  
     |   +---+ +---+    +---+ +---+           |
     |   |121|-|131|    |211| |221|           |                        Level 3                                 
     |   +---+ +---+    +---+ +---+           |
     |           |--------|------|            |
     |-----------|----------------------------|     


 |     Group 0       |       group 1     |      group 2       |
'''

Networkx で作成します。

# create it in networkx
import networkx as nx
G = nx.DiGraph()
G.add_edges_from([('0', '1'), ('0', '2'), ('0', '3')])
G.add_edges_from([('1', '11'), ('1', '12'), ('1', '13')])
G.add_edges_from([('2', '21'), ('2', '22'), ('2', '23')])
G.add_edges_from([('3', '31'), ('3', '32'), ('3', '33')])
#
G.add_edges_from([('12', '121'), ('13', '131')])
G.add_edges_from([('12', '121'), ('13', '131')])
G.add_edges_from([('21', '211'), ('22', '221')])
#
G.add_edges_from([('13', '121')])  
G.add_edges_from([('21', '131')])  
G.add_edges_from([('131', '211')])  
G.add_edges_from([('131', '221')])

#
G.add_edges_from([('121', '13')])            # node may not with "in_degree" link only
G.add_edges_from([('131', '21')])            # ditto

#
G.add_edges_from([('131', '31')]) 
G.add_edges_from([('131', '11')])
G.add_edges_from([('11', '131')])

#
G.add_edges_from([('121', '131')])

質問:

以下のノードをサンプルとして使用して、グラフ内のノードとエッジを見つける方法:

「121」、同じグループ内の上位レベルへのリンクが複数ありますか? (ノードエッジタイプ「不明」、in_degree または out_degree またはその両方、次の質問と同じ)
「131」、他のグループへのより高いレベルのノードへのリンクが複数ありますか?
「131」、同じグループ内の同じレベルのノードへのリンクあり
「131」、同じレベルのノードへのリンクがあるが、他のグループにある
「21」、異なるグループの下位ノードへのリンクあり

「Graph」を初めて使用し、サンプルコードを取得して、networkx の使用方法を詳しく調べます。

どうもありがとう。

score 2 · Accepted Answer

最初に、ノードがどのグループまたはレベルにあるかを何らかの形で定義する必要があります。これは、ツリー構造を破壊する追加のエッジのためにグラフ istelf で定義されていないためです。私はちょうどあなたの命名パターンに従い、これらのヘルパー関数を書いて、与えられた名前をレベル/グループに変換しました:

def get_group(node):
    if node == '0':
        return 1
    return int(node[0])-1

def get_level(node):
    if node == '0':
        return 0
    return len(node)

def equal_group(a,b):
    return get_group(a) == get_group(b)

def lower_level(a,b):
    return get_level(a) < get_level(b)

def equal_level(a,b):
    return get_level(a) == get_level(b)

次に、指定に従ってノードをフィルタリングできます。

def filter_q1(node):
    k = len([predecessor for predecessor in G.predecessors_iter(node) if equal_group(node, predecessor) and lower_level(predecessor, node)] )
    return k > 1
q1_result = filter(filter_q1, G)
print 'Q1:', q1_result


def filter_q2(node):
    k = len([predecessor for predecessor in G.predecessors_iter(node) if lower_level(predecessor, node)])
    return k > 1
q2_result = filter(filter_q2, G)
print 'Q2:', q2_result


def filter_q3(node):
    k = len([neighbour for neighbour in G.neighbors_iter(node) if equal_level(node, neighbour) and equal_group(node, neighbour)])
    return k > 0
q3_result = filter(filter_q3, G)
print 'Q3:', q3_result


def filter_q4(node):
    k = len([neighbour for neighbour in G.neighbors_iter(node) if equal_level(node, neighbour)])
    return k > 0
q4_result = filter(filter_q4, G)
print 'Q4:', q4_result


def filter_q5(node):
    k = len([neighbour for neighbour in G.neighbors_iter(node) if not equal_group(node, neighbour)])
    return k > 0
q5_result = filter(filter_q5, G)
print 'Q5:', q5_result

結果は次のようになります。

>>>Q1: ['131', '121']
>>>Q2: ['131', '121']
>>>Q3: ['121']
>>>Q4: ['131', '121']
>>>Q5: ['21', '131', '0']

一般に、不要なエッジは次のように見つけることができます。

def is_bad_edge(edge):
    a, b = edge
    if not equal_group(a, b):
        return True
    if not lower_level(a, b):
        return True
    return False
bad_edges = filter(is_bad_edge, G.edges_iter())
print 'Bad edges:', bad_edges

これにより、結果として：

>>>Bad edges: [('21', '131'), ('131', '11'), ('131', '31'), ('131', '21'), ('131', '221'), ('131', '211'), ('121', '13'), ('121', '131'), ('0', '1'), ('0', '3')]

0ご覧のとおり、グループ 1 として分類されているため、元のエッジもそこにありますが、ノード1とノード3はそうではありません。ノードを分類する方法に応じて0、関数を調整してルートノードを含めたり除外したりできます。

score 2 · Accepted Answer

このようなものがうまくいくかもしれません。ノードの長さをレベルとして使用し (それを機能させるには、コード内のレベル 0 ノードをコメントアウトする必要がありました)、ノード文字列の最初の要素をグループとして使用します。それがあなたのデータ構造で意図したものだと思います。

# create it in networkx
import networkx as nx
G = nx.DiGraph()
#G.add_edges_from([('0', '1'), ('0', '2'), ('0', '3')])
G.add_edges_from([('1', '11'), ('1', '12'), ('1', '13')])
G.add_edges_from([('2', '21'), ('2', '22'), ('2', '23')])
G.add_edges_from([('3', '31'), ('3', '32'), ('3', '33')])
#
G.add_edges_from([('12', '121'), ('13', '131')])
G.add_edges_from([('12', '121'), ('13', '131')])
G.add_edges_from([('21', '211'), ('22', '221')])
#
G.add_edges_from([('13', '121')])
G.add_edges_from([('21', '131')])
G.add_edges_from([('131', '211')])
G.add_edges_from([('131', '221')])

#
G.add_edges_from([('121', '13')])            # node may not with "in_degree" link only
G.add_edges_from([('131', '21')])            # ditto

#
G.add_edges_from([('131', '31')])
G.add_edges_from([('131', '11')])
G.add_edges_from([('11', '131')])
G.add_edges_from([('121', '131')])

# "121", with more than one link to higher level in same group? (node edge type "unsure", may in_degree or out_degree or both, same in following question)

print "more than one link to higher level in same group"
for node in G:
    l = len(node)-1 # higher level
    others = [n for n in G.successors(node)+G.predecessors(node)
              if len(n)==l and n[0]==node[0]]
    if len(others) > 1:
        print node

# "131", with more than one link to higner level nodes to other group?
print "more than one link to higher level in same group"
for node in G:
    l = len(node)-1 # higher level
    others = [n for n in G.successors(node)+G.predecessors(node)
              if len(n)==l and n[0]!=node[0]]
    if len(others) > 1:
        print node


# "131", with links to same level nodes in same group
print "same level, same group"
for u,v in G.edges():
    if len(u) == len(v):
        if u[0] == v[0]:
            print u

# "131", with links to same level nodes but in other group
print "same level, other group"
for u,v in G.edges():
    if len(u) == len(v):
        if u[0] != v[0]:
            print u


# "21", with links to lower level nodes in different group
print "same level, other group"
for u,v in G.edges():
    if len(u) == len(v)-1:
        if u[0] != v[0]:
            print u

python - networkxのルールで不適切なノードを見つけますか?

2 に答える 2

Related

Reference