0

数百万のエッジを持つ有向グラフが与えられた場合、ノードごとに見つけようとしています。

  1. 隣人の隣人のリスト (それらを呼びましょうtwo_nei)。

  2. two_nei( と呼ばれる)のそれぞれとの共通の近隣の数cn。

私がこの問題にアプローチしている方法は次のとおりです。

  1. dict各ノードをキーとして を作成し、listすべての隣接ノードを値として含む を作成します ( neighbor_dictionary)。

  2. dict各ノードをキーとして を作成しlist、ネイバーのすべてのネイバー (two_neiこのノードの) を値として含む を作成します ( second_dictionary)。

  3. 今、グラフ内のすべてのノードを使用して、 list(何をすべきかわからないため)を作成したいと考えています。dictこれらの各辞書には、各two_neiノードがキーとして含まれ、値はそれらが持つ共通の近隣の数になります。

ご覧のとおり、これは簡単に複雑になります。Pythonでこれを行うには、よりシンプルでエレガントな方法があると確信しています。私は数学が得意で、データ構造にもアルゴリズムにもクラスはありませんでしたが、キューを使用してこれを解決できると確信しています。

どんな助けでも大歓迎です。

4

2 に答える 2

2

グラフ内の 2 つのノードの共有される 2 番目の隣接ノードの数を返す関数を次に示します。グラフにはnetworkxを使用します。各ノードのデータ量とグラフの接続密度によっては、メモリ内に大きなセットが作成される可能性があるため、これが機能しない場合があります。

def num_shared_second_neighbors(graph, node1, node2):
    """Number of second neighbors shared by node1 and node2 in graph."""
    return len(set(second_neighbors(graph, node1)).intersection(set(second_neighbors(graph, node2))))

def second_neighbors(graph, node):
    """Yield second neighbors of node in graph.
    Neighbors are not not unique!
    """
    for neighbor_list in [graph.neighbors(n) for n in graph.neighbors(node)]:
        for n in neighbor_list:
            yield n

この関数second_neighborsは、単純なグラフ トラバーサルを実行することにより、ノードの一意ではない 2 番目の近傍を生成するジェネレータです。この関数num_shared_second_neighborsは、単純に、2 つのノードの秒の隣接セットの交点にあるノードの数を返します。

于 2012-06-24T04:06:54.043 に答える
0

NetworkXで書かれた目的の関数は次のとおりです。

1.隣人の隣人のリスト

def get_second_neighbors(graph, node) -> list:
    """
    Returns a list of unique second neighbors for a given node in the graph.
    """
    return [second_neighbor 
            for first_neighbor in graph.neighbors(node)
            for second_neighbor in graph.neighbors(first_neighbor) 
            if second_neighbor != node])

2. 共有ネイバーの数

def get_num_shared_neighbors(graph, node1, node2) -> int:
    """
    Returns a number of second neighbors shared by node1 and node2 in the graph.
    """
    return len(set.intersection(set(get_second_neighbors(graph, node1)), 
                                set(get_second_neighbors(graph, node2))))

リストの理解により、リストがエレガントで理解しやすくなったことを願っています。

于 2021-04-15T04:36:18.870 に答える