【Python】 k-hop Clusteringの詳説：ネットワークグラフにおけるクラスタリング手法の実装と解説

ネットワーク分析手法：k-hop Clusteringの実装・解説

k-hop Clusteringとは

k-hop Clusteringは、ネットワークグラフにおけるクラスタリング手法の一つです。この手法の特徴は、ネットワーク上の任意のノードから指定した数（k）のエッジを辿って到達できるノードを1つのクラスタとして抽出できる点にあります。

具体的な例で見るk-hop Clustering

1-hopクラスタリングの場合

あるノードから1エッジで到達できるノードのみをクラスタとして抽出します。例えば：

• 中心ノード「A」から
• 直接つながっているノード「B」「C」「D」が
• 1つのクラスタとして抽出されます

2-hopクラスタリングの場合

1-hopの範囲をさらに1エッジ分広げ、2エッジ以内で到達可能なノードまでをクラスタとして抽出します。

基本的な処理の流れ

今回実装したk-hop Clusteringは以下の3つのステップで実行されます：

1. クラスタの抽出
2. k-1エッジ以内で完結するクラスタの除去
3. 重複クラスタの削除

プログラム全文

#khopClustering.py
#k-hop clusteringの実装
#流れ：クラスタの抽出→指定のエッジ数の広がりをもつクラスタのみを抽出→重複を削除
import sys
import pandas as pd
from sklearn.cluster import MiniBatchKMeans
import networkx as nx
import os
import glob
from collections import defaultdict
import os
import shutil
import sys

args = sys.argv

#グラフの定義
print("start")
df = pd.read_table(R"list\ComplexProtein_data_bidir.tsv")
G = nx.from_pandas_edgelist(df,
                            source='query',
                            target='target',
                            )

#リストの定義
clusters = []
queries = []

#radius_valueでkの値をコントロールできる
for radius_value in range(1,int(args[1])):
    directory = "copro_" + str(radius_value) + "edge"
    directory2 = "copro_only" + str(radius_value) + "edge"
    if not os.path.exists(directory):
        os.mkdir(directory)
    if not os.path.exists(directory2):
        os.mkdir(directory2)
#G（ネットワークグラフ）の各ノードをクエリにいれてループを回す
#queriesリストは後で参照する用
    for query in G.nodes():
        queries.append(query)
        #ego_graghを用いることでループ内のqueryを中心としたエゴネットワークが作成される
        #そのネットワークは半径radius_valuse（radius_value個のエッジ）でつながることができるもののみのネットワークとする
        subgraph = nx.ego_graph(G, query, radius = radius_value)
        #clustersリストにsubgraghのノードをリスト化したものを追加する
        #つまり，clustersリストの中にsubgraphのノードのリストを入れる
        clusters.append(sorted(list(subgraph.nodes())))

    for i, cluster in enumerate(clusters):
        query2 = queries[i]

        central_node = list(nx.ego_graph(G, cluster[0], radius=1).nodes())[0]
        #query2= queries[]をファイル名にすることで，どのファイルにどのクエリを中心とするクラスタが入っているのかを明示する
        filename = f"copro_{radius_value}edge\cluster_{query2}.csv"

        #書き込み
        cluster_df = pd.DataFrame(cluster, columns=["node"])
        cluster_df.to_csv(filename, index=False)

    #ここまででクラスタの抽出完了

    #フォルダ内を比較して，同じクラスタがあれば出力しない
    #異なるクラスタであれば行数が多いほう（エッジ数が多いほう）を出力する
    #エッジ数が3のみのクラスタとかが出力できる

    #1edgeの結果のソート
    if radius_value == 1:
        sort_directory = "copro_1edge"
        output_sort_directory = "copro_only" + str(radius_value) + "edge"

        files = glob.glob(os.path.join(sort_directory, "cluster_*.csv"))
        for file in files:
        # ファイルの読み込み
            with open(file, "r") as f:
                lines = f.readlines()

            # ファイル内容のソート
            lines.sort()

            # 新しいファイル名を作成する
            filename = os.path.basename(file)

            # 新しいファイルに書き込む
            with open(os.path.join(output_sort_directory, filename), "w") as f:
                f.writelines(lines)
    else:

        folder1 = "copro_" + str(radius_value) + "edge"
        folder2 = "copro_" + str((radius_value - 1)) + "edge"
        output_folder = "copro_only" + str(radius_value) + "edge"

        file_dict = defaultdict(list)

        # folder1とfolder2のファイル名を対応付ける
        for file in os.listdir(folder1):
            if file in os.listdir(folder2):
                file_dict[file].append(folder1)
                file_dict[file].append(folder2)

        # 同名ファイルを比較し、出力
        for file, folders in file_dict.items():
            with open(os.path.join(folders[0], file)) as f1, open(os.path.join(folders[1], file)) as f2:
                content1 = sorted(f1.read().split("\n"))
                content2 = sorted(f2.read().split("\n"))

            if content1 != content2:
                # 中身が異なれば、行数の多いほうを出力
                if len(content1) > len(content2):
                    out_content = "\n".join(content1)
                else:
                    out_content = "\n".join(content2)

                with open(os.path.join(output_folder, file), "w") as f:
                    f.write(out_content)

    #フォルダ内の中身重複ファイルを一つにまとめるプログラム

    input_dir = "copro_only" + str(radius_value) + "edge"
    output_dir = "copro_only" + str(radius_value) + "edge_zyuhukunashi"

    # 入力CSVファイルを全て読み込む
    files = {}
    for f in os.listdir(input_dir):
        if f.endswith(".csv"):
            with open(os.path.join(input_dir,f)) as fp:
                content = fp.read()
                content = "".join(sorted(content.split("\n"))) # ソート
            files[f] = content

    # 内容が重複するファイルをチェック
    rep_files = {}
    for f1 in files:
        if files[f1] not in rep_files:
            rep_files[files[f1]] = f1

    # 代表ファイルのみを出力フォルダにコピー
    if not os.path.exists(output_dir):
        os.mkdir(output_dir)

    for content, f in rep_files.items():
        shutil.copy(os.path.join(input_dir, f), output_dir)

#余計なフォルダを削除
for radius_value in range(1,int(args[1])):
    shutil.rmtree("copro_" + str(radius_value) + "edge")
    shutil.rmtree("copro_only" + str(radius_value) + "edge")

実装のポイント

1. クラスタ抽出の核となる処理

NetworkXのego_graphを活用したクラスタ抽出

subgraph = nx.ego_graph(G, query, radius = radius_value)
clusters.append(sorted(list(subgraph.nodes())))

このコードブロックが実装の中核です：

• ego_graph：中心ノードから指定半径内のサブグラフを抽出
• radius：k-hopにおけるkの値を指定
• sorted(list())：ノードリストをソートして保存（後の比較処理のため）

2. k-hopごとのクラスタ処理

段階的なクラスタ抽出

for radius_value in range(1, int(args[1])):
    directory = "copro_" + str(radius_value) + "edge"
    directory2 = "copro_only" + str(radius_value) + "edge"

• 1-hopから順番にクラスタを抽出
• 各hopごとに専用のディレクトリを作成
• 中間結果と最終結果を分けて保存

3. クラスタの選別処理

k-1との比較による選別

if content1 != content2:
    if len(content1) > len(content2):
        out_content = "\n".join(content1)
    else:
        out_content = "\n".join(content2)

重要な選別ロジック：

1. k-hopとk-1hopのクラスタを比較
2. 内容が異なる場合のみ処理
3. より大きいクラスタを採用

4. 重複クラスタの除去

内容ベースの重複判定

files = {}
for f in os.listdir(input_dir):
    if f.endswith(".csv"):
        with open(os.path.join(input_dir,f)) as fp:
            content = fp.read()
            content = "".join(sorted(content.split("\n")))
        files[f] = content

rep_files = {}
for f1 in files:
    if files[f1] not in rep_files:
        rep_files[files[f1]] = f1

重複除去の仕組み：

1. クラスタの内容をソートして文字列化
2. 内容をキーとしてディクショナリ化
3. 同一内容の場合は1つだけを代表として保持

5. ファイル管理の最適化

一時ファイルの管理

for radius_value in range(1,int(args[1])):
    shutil.rmtree("copro_" + str(radius_value) + "edge")
    shutil.rmtree("copro_only" + str(radius_value) + "edge")

処理の効率化：

• 中間ファイルを段階的に作成
• 処理完了後に不要なディレクトリを削除
• ディスク容量の効率的な利用

手法の特徴

メリット

• ネットワーク構造を考慮した自然なクラスタリングが可能
• 遠距離の弱い関係性も検出できる
• エッジ数による制御が容易

現状の課題

本手法には以下のような課題があります：

1. 類似クラスタの判定
   • メンバーが1つだけ異なるクラスタでも別クラスタとして判定
   • 例：ノードAを中心としたクラスタとノードBを中心としたクラスタが、ほぼ同じメンバーで構成されていても別クラスタとして抽出

改善の方向性

1. クラスタの類似度評価

• Jaccard係数などの類似度指標の導入
• 類似度に基づくクラスタの統合処理

2. 処理の効率化

• 並列処理による高速化
• メモリ使用量の最適化

3. クラスタ品質の評価

• クラスタ密度の計算
• クラスタ間の独立性評価

まとめ

k-hop Clusteringは、ネットワーク構造に基づいて自然なクラスタリングを行うことができる手法です。実装は比較的シンプルですが、類似クラスタの扱いには注意が必要です。今後は、類似度評価やクラスタ品質の評価機能を導入することで、より精度の高いクラスタリングが期待できます。