グラフ理論の最小経路(ソーシャルネットワーク分析)

graph-theory social-networking
グラフ理論の最小経路(ソーシャルネットワーク分析)

これはシナリオです。n個のノードとe個のエッジを持つ無向グラフがあり、すべてのノードが接続されています。

シナリオの質問:すべてのノードは、コンテンツを共有または読み取るソーシャルネットワークの人物と見なすことができます。 これは、AがB、C、Dに接続されている場合、Aがネットワークとコンテンツを共有している場合、直接BCDに到達することを意味します。 つまり、ネットワーク内のすべてのノードに到達するには、コンテンツを共有するノードに隣接している必要があります。

Q1:ネットワーク全体に到達するための最適な出発点を見つける方法はありますか? Q2:そのポイントから最小のパスを見つける方法はありますか?

私はすでにセールスマンの問題と原始アルゴリズムを見てきました。

ありがとうございます。

  0  0


ベストアンサー

Centralityのウィキペディアページは、グラフの中心性のいくつかの異なる形式を説明し、それらのいくつかのアルゴリズムへのリンクを持っています。

2


ネットワークの隣接行列をn乗すると、2つの頂点i、j(行列のij番目の要素で表される)の間の長さnのウォーク数が得られます。 x(i、j)の最初のゼロ以外の値は、ウォークに関してどれだけ離れているかを示します。 ネットワーク全体に到達するのに最適なノードを探している場合は、nを増やしながらゼロ以外の値をすべて持つ行列の行(または列)の最初のインスタンスを探すことができます。

明らかに、これは巨大なネットワークでは実用的ではありません…​

そうでなければ、ダイクストラのアルゴリズムを適用できます。

1


Closeness Centralityは個々のノードのランキングであり、「ノードがネットワークの中心にどれだけ近いか」の尺度として考えることができます。 そのため、近接中心性の値が高いノードは、ネットワーク内の他のすべてのノードに到達するために、このノードが(平均して)より少ない数の希望を取るようにネットワークに配置されます。 したがって、上記のQ1の場合、最も近いノードを持つノードは、途中のノード間の最小ホップ数で他のすべてのノードに到達するのに最適な位置にあると解釈できます。 Q2の場合、「最小パス」は、ネットワーク内のすべてのノードへの最小平均パスと見なすことができます。

0


タイトルとURLをコピーしました