複数のアルゴリズムの動的な表示を実装するこのPythonライブラリは、ネットワークグラフのコミュニティ構造を発見するのに役立ちます。

[[382977]]

コミュニティ発見アルゴリズムに精通しているなら、この Python ライブラリを見逃すことはできません。 LouvainアルゴリズムやGirvan-Newmanアルゴリズムなどのさまざまなコミュニティ発見アルゴリズムをカバーし、可視化機能も備えています。

ネットワークは、密接に接続された多数のノードで構成されており、異なるノード間の接続の程度に応じて、ネットワークは異なるクラスターで構成されていると考えることもできます。クラスター内のノードはより密接に接続されていますが、異なるクラスター間の接続は比較的疎です。このようなクラスターは、ネットワーク内のコミュニティ構造と呼ばれます。

これから派生したコミュニティ検出アルゴリズムは、ネットワーク内のコミュニティ構造を検出するために使用されます。このようなアルゴリズムには、Louvain アルゴリズム、Girvan-Newman アルゴリズム、Bron-Kerbosch アルゴリズムなどがあります。

最近、Machine Heart は、グラフ内のコミュニティ構造を検出できる、communities という Python ライブラリを GitHub で発見しました。このライブラリは、ソフトウェア エンジニアの Jonathan Shobrook によって作成されました。

プロジェクトアドレス: https://github.com/shobrook/communities

まず、ライブラリは次のコミュニティ検出アルゴリズムを実装できます。

• ルーヴァンアルゴリズム
• ガーバン・ニューマンアルゴリズム
• 階層的クラスタリング
• スペクトルクラスタリング
• ブロン・ケルボッシュアルゴリズム

次に、ユーザーはコミュニティ ライブラリを使用して、上記のアルゴリズムを視覚化することもできます。次の図は、Zachary の空手クラブ ネットワークにおける Louvain アルゴリズムの視覚化結果を示しています。

このライブラリのインストール方法も非常に簡単です。コミュニティをインストールするには、pip を使用します。コードは次のとおりです。

 $ pip インストールコミュニティ

多くのネットユーザーがこの Python ライブラリを高く評価し、試してみると述べました。

アルゴリズムの詳細な説明

ルーヴァンアルゴリズム

louvain_method(adj_matrix: numpy.ndarray, n: int = None) -> リスト

このアルゴリズムは、「大規模ネットワークにおけるコミュニティの高速展開」という記事 (略称 Louvian) から引用したものです。

モジュール性に基づくコミュニティ発見アルゴリズムとして、Louvain アルゴリズムは効率性と有効性の面で比較的優れたパフォーマンスを発揮し、階層的なコミュニティ構造を発見することができます。その最適化目標は、グラフ属性構造 (コミュニティ ネットワーク) 全体のモジュール性を最大化することです。

Louvain アルゴリズムは、グラフのモジュール性を最大化するコミュニティを貪欲に検索します。グラフのグループ内エッジの密度が高く、グループ間エッジの密度が低い場合、そのグラフはモジュール グラフと呼ばれます。

サンプルコードは次のとおりです。

 community.algorithms から louvain_methodadをインポートします
j_matrix = [...]
コミュニティ、_ = louvain_method(adj_matrix)

ガーバン・ニューマンアルゴリズム

girvan_newman(adj_matrix: numpy.ndarray, n: int = None) -> リスト

このアルゴリズムは、「社会的および生物学的ネットワークにおけるコミュニティ構造」という記事から引用したものです。

Girvan-Newman アルゴリズムは、エッジを繰り返し削除して、より接続されたコンポーネントを作成します。各コンポーネントはコミュニティとして扱われ、モジュール性をこれ以上増加できなくなった時点でアルゴリズムはエッジの削除を停止します。

サンプルコードは次のとおりです。

 community.algorithms から girvan_newmanをインポートします
adj_matrix = [...]
コミュニティ、_ = girvan_newman(adj_matrix)

階層的クラスタリング

hierarchical_clustering(adj_matrix: numpy.ndarray、metric: str = "cosine" 、linkage: str = "single" 、n: int = None) -> list

階層的クラスタリングは、ボトムアップの階層的クラスタリング アルゴリズムを実装します。各ノードは独自のコミュニティから始まり、階層が構築されるにつれて、最も類似したコミュニティが統合されます。モジュール化がこれ以上進展しなくなるまで、コミュニティは統合されます。

サンプルコードは次のとおりです。

 community.algorithms から hierarchical_clusteringをインポートします
adj_matrix = [...]
コミュニティ = hierarchical_clustering(adj_matrix、メトリック = "ユークリッド" 、リンク = "完全" )

スペクトルクラスタリング

spectral_clustering (adj_matrix: numpy.ndarray, k: int ) -> リスト

このタイプのアルゴリズムでは、隣接行列の固有値にコミュニティ構造に関する情報が含まれていると想定しています。

サンプルコードは次のとおりです。

 community.algorithms から spectral_clusteringをインポートします
adj_matrix = [...]
コミュニティ = スペクトルクラスタリング(adj_matrix, k= 5 )

ブロン・ケルボッシュアルゴリズム

bron_kerbosch(adj_matrix: numpy.ndarray、pivot: bool = False) -> リスト

最大クリーク検出のための Bron-Kerbosch アルゴリズムの実装。グラフ内の最大クリークは、完全なグラフを形成するノードのサブセットであり、このサブセットにノードを追加すると、完全ではなくなります。クリークはグラフ内で最も密接に接続されたノードのグループであるため、最大のクリークをコミュニティと見なすのが妥当です。ノードは複数のコミュニティのメンバーになることができるため、アルゴリズムは重複するコミュニティを識別することがあります。

サンプルコードは次のとおりです。

 community.algorithms から bron_kerboschをインポート
adj_matrix = [...]
コミュニティ = bron_kerbosch(adj_matrix, pivot=True)

視覚化

描画

draw_communities(adj_matrix: numpy.ndarray、コミュニティ: リスト、dark: bool = False、ファイル名: str = None、シード: int = 1 )

グラフを視覚化し、ノードを所属するコミュニティごとにグループ化し、色分けします。プロットを表す matplotlib.axes.Axes を返します。サンプルコードは次のとおりです。

 community.algorithms から louvain_methodをインポートします
community.visualization から draw_communitiesをインポートします
adj_matrix = [...]
コミュニティ、フレーム = louvain_method(adj_matrix)
 draw_communities(adj_matrix、コミュニティ)

視覚化は次のようになります。

ルーヴァンアルゴリズムのアニメーションイラスト

louvain_animation(adj_matrix: numpy.ndarray、フレーム: リスト、dark: bool = False、duration: int = 15 、filename: str = None、dpi: int = None、seed: int = 2 )

グラフに Louvain アルゴリズムを適用すると、アニメーション化されたグラフィック表示を実装できます。各ノードの色は、そのノードが属するコミュニティを表し、同じコミュニティ内のノードはクラスター化されます。

サンプルコードは次のとおりです。

 community.algorithms から louvain_methodをインポートします
community.visualization から louvain_animationをインポート
adj_matrix = [...]
コミュニティ、フレーム = louvain_method(adj_matrix)
 louvain_animation(adj_matrix、フレーム)

アニメーション画像を以下に示します。