Neo 4 j強連通成分アルゴリズムについて、どのくらい知っていますか?

図アルゴリズムは、リソースまたは情報ストリーム、伝染またはネットワーク障害の伝播の経路、および集団への影響および弾性などの複雑な動的を理解し、モデリングし、予測する手段を提供する.
このブログシリーズは、Neo 4 jなどの図データベースを使用して、スマートソリューションをより迅速かつ効果的に革新し、開発できるように、読者が図分析と図アルゴリズムをよりよく利用できるようにすることを目的としています.
先週,中心性(Centrality)アルゴリズムの研究をまとめ,親密中心性(Closeness Centrality)アルゴリズムも研究した.
今週、コミュニティ発見(Community Detection)アルゴリズムの研究を開始し、各ノードが同じグループの他の各ノードから到着できるように、関係の方向に基づいてノードグループを位置決めするStrongly Connected Components(SCC)アルゴリズムを強化しました.通常、深度優先検索に適用されます.
強連通成分について
強連通成分アルゴリズムは、各ノードが同じ集合の他の任意のノードから2方向に到達することができる接続ノードの集合を図に示す.通常、図分析の過程で初期に使用され、図の構造を理解するためによく使われています.
SCCは最も古いグラフィックアルゴリズムの1つであり,Tarjanは1972年に最初の線形時間アルゴリズムを記述した.有向図を強い連通成分に分解することは深さ優先探索アルゴリズムの古典的な応用である.
強い連通成分はいつ使うべきですか?

強力な多国籍企業の分析では、SCCは各メンバーが他のメンバーの株式を直接所有および/または間接的に所有する会社の集合を検索するために使用されます.取引コストの削減、信頼の増加などの利点がありますが、このような構造は市場競争を弱めています.詳細については、「グローバルエンタープライズ・コントロール・ネットワーク」(The Network of Global Corporate Control)を参照してください.http://u6.gg/rDnrz](http://u6.gg/rDnrz

がマルチホップ無線ネットワークにおいてルーティング性能を測定するとき、SCCは、異なるネットワーク構成の接続性を計算するために使用されている.詳細については、「マルチホップワイヤレスネットワークに一方向リンクが存在する場合のルーティングパフォーマンス」(Routing performance in the presence of unidirectional links in multihop wireless networks)を参照してください.http://u6.gg/rDnun

強連通成分アルゴリズムは、通常、多くの図アルゴリズムの第1のステップとして使用され、これらのアルゴリズムは強接続図にのみ適用される.ソーシャルネットワークでは、多くの人が密接な関係を持っています(例えば、クラスや他の公共の場所の学生).これらのグループの多くの人は、一般的なサイトや一般的なゲームが好きです.SCCアルゴリズムは、このようなグループを見つけ、これらのサイトやゲームがまだ好きではないグループにこれらのコンテンツを推薦するために使用される.

強連通成分の例
強連通成分アルゴリズムの実際の応用を見てみましょう.次のCypher文は、ユーザーとユーザーの間のFOLLOW関係を含むTwitterスタイルの図を作成します.

MERGE (nAlice:User {id:\u0026quot;Alice\u0026quot;})MERGE (nBridget:User {id:\u0026quot;Bridget\u0026quot;})MERGE (nCharles:User {id:\u0026quot;Charles\u0026quot;})MERGE (nDoug:User {id:\u0026quot;Doug\u0026quot;})MERGE (nMark:User {id:\u0026quot;Mark\u0026quot;})MERGE (nMichael:User {id:\u0026quot;Michael\u0026quot;})MERGE (nAlice)-[:FOLLOWS]-\u0026gt;(nBridget)MERGE (nAlice)-[:FOLLOWS]-\u0026gt;(nCharles)MERGE (nMark)-[:FOLLOWS]-\u0026gt;(nDoug)MERGE (nMark)-[:FOLLOWS]-\u0026gt;(nMichael)MERGE (nBridget)-[:FOLLOWS]-\u0026gt;(nMichael)MERGE (nDoug)-[:FOLLOWS]-\u0026gt;(nMark)MERGE (nMichael)-[:FOLLOWS]-\u0026gt;(nAlice)MERGE (nAlice)-[:FOLLOWS]-\u0026gt;(nMichael)MERGE (nBridget)-[:FOLLOWS]-\u0026gt;(nAlice)MERGE (nMichael)-[:FOLLOWS]-\u0026gt;(nBridget);

これで、強い連通コンポーネントを実行して、各人が相互にリンクしているかどうかを確認し、次のクエリを実行できます.

CALL algo.scc.stream(\u0026quot;User\u0026quot;,\u0026quot;FOLLOWS\u0026quot;)YIELD nodeId, partitionMATCH (u:User) WHERE id(u) = nodeIdRETURN u.id AS name, partition

強連通成分の可視化
我々の例図には3つの強い連通成分がある.
1つ目も最大のコンポーネントで、メンバーのAlice、Bridget、Michaelがあり、2つ目のコンポーネントはDougとMarkがあります.Chariesは最終的には自分のコンポーネントにのみ存在し,そのノードから他のノードまでの間には関係が伝達されないためである.
結論
我々が見たように,強い連通成分アルゴリズムは,通常,識別されたクラスタ上で他のアルゴリズムを独立に実行するために用いられる.図面への前処理ステップとして、切断された接続のグループを迅速に識別するのに役立ちます.
テキストリンク:https://neo4j.com/blog/graph-algorithms-neo4j-strongly-connected-components/