枝集合が単調増加するグラフの平均クラスタ係数更新方法

平均クラスタ係数とは
枝集合の単調増加
実装
- 保持情報
- 枝増加時の更新
テスト
- コード
- 出力
まとめ
参考

平均クラスタ係数とは

グラフ構造の特徴づけ指標の一つです. ノードごとに, そのノードを含む三角形(クリーク)の割合を算出します. 具体的にはグラフ $G = (V, E)$ , ノード $u \in V$ について, $u$ と隣接するノードからなるノード集合 $V'$ から制限される部分グラフ $G' = (V', E')$ について

$\cfrac{{\rm uを含むクリーク(三角形)数}}{{\rm uを含む3点の選び方の組み合わせ数}}$

をノード $u$ のクラスタ係数として, 全てのノードのクラスタ係数の平均を最終的に計算します.

詳細はこちら

具体的な計算はクリークの数え上げになるので, グラフの隣接行列の3乗を計算し, その行列の対角成分のカウントを行えば十分です.

枝集合の単調増加

ここでは, グラフに枝が1本追加された場合のクラスタ係数の変化を考察します. もしグラフに枝が1本追加された場合のクラスタ係数の更新が(行列の3乗計算よりも)効率よく行うことができれば, 複数枝が増えた場合にも, 全てのノードに対しクラスタ係数を計算し直さなくても逐次的にクラスタ係数を更新することで計算量を抑えることができます.

ここでは枝(u, v)がグラフに追加された場合を考えることにします.

$G = (V, E \cup (u, v))$

ここでクラスタ係数に影響が出るノードは下記の2種類.

追加された枝の始点終点のどちらにもつながる点
追加された枝の始点終点

そのとき, 増加するクリーク数は, 1. の場合は1, 2の場合は u の隣接ノード集合と v の隣接ノード集合の共通部分の大きさ, となるのは簡単に確かめられます.

f:id:inarizuuuushi:20211016165448p:plain

またクラスタ係数を計算する際の, 分母はノードuの隣接ノード集合の大きさから算出できます.

実装

保持情報

上記の考察をもとに, クラスタ係数を更新するには, 隣接ノード集合と現在のクリーク数を保存しておけばよさそうです.

class AdjacentData:
    """
    Attributes
    ----------
    ad_set : set
        set of adjacent nodes
    n_pair : int
        number of pair of adjacent nodes
    n_clique : int
        number of clique of adjacent nodes
    n_ad : int
        number of adjacent nodes
    """
    def __init__(self, ad_set, n_pair, n_clique):
        self.ad_set = ad_set
        self.n_pair = n_pair
        self.n_clique = n_clique
        self.n_ad = len(ad_set)

    def add_ad(self, other, other_ad_set):
        """add adjacent node
        Parameters
        ----------
        other : any
            node-id
        other_ad_set : set
            set of other's adjacent nodes
        """
        self.n_ad += 1
        self.n_pair = self.n_ad * (self.n_ad - 1) // 2
        self.n_clique += len(self.ad_set & other_ad_set)
        self.ad_set.add(other)
    
    def score(self):
        """calculate clustering score
        
        Returns
        -------
        float
            clustering score, n_clique / n_pair
        """
        return self.n_clique / self.n_pair if self.n_pair > 0 else 0
    
    def __str__(self):
        return (
            f"n_pair {self.n_pair:2d},"
            +f" n_clique {self.n_clique:2d},"
            +f" n_ad {self.n_ad},"
            +f" ad_set {self.ad_set}"
        )

枝増加時の更新

# node_info: dict key is node-id, value is AdjacentData

# u, v は増加した枝の端点
# case 2
node_info[u].add_ad(v, node_info[v].ad_set)
node_info[v].add_ad(u, node_info[u].ad_set)

# case 1 u - w - v
for w in node_info[u].ad_set & node_info[v].ad_set:
    node_info[w].n_clique += 1

テスト

テストでは, ノード同士の距離がk以下だったら枝をはるというルールでそのkを単調増加させながら, グラフの更新, 及びそれぞれのノードのクラスタ係数の更新を行っています.

コード

import itertools
import collections

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

pos = {
    0: np.array([0,   0  ]),
    1: np.array([0.5, 0  ]),
    2: np.array([1,   2.1]),
    3: np.array([1.3, 0.9]),
}
n_node = 4  # ノード数
G = nx.Graph()
G.add_nodes_from(pos.keys())

## ノード

fig, ax = plt.subplots()
nx.draw_networkx_edges (G, pos, edge_color='y', ax=ax)
nx.draw_networkx_nodes (G, pos, node_color='r', alpha=0.5, ax=ax)
nx.draw_networkx_labels(G, pos, font_size=10)

## ノードペアを距離ソート

Pair = collections.namedtuple("Pair", "distance first second")

sorted_pairs = sorted([
    Pair(np.linalg.norm(pos[i] - pos[j]), i, j)
    for i, j in itertools.combinations(range(n_node), 2)
])
# print(sorted_pairs)

## 閾値リスト

min_distance = sorted_pairs[0].distance
max_distance = sorted_pairs[-1].distance
n_threashold = 4  # 閾値数
threasholds = np.linspace(min_distance, max_distance, n_threashold)
# print(threasholds)

## 平均クラスタ計算用管理

class AdjacentData:
    """
    Attributes
    ----------
    ad_set : set
        set of adjacent nodes
    n_pair : int
        number of pair of adjacent nodes
    n_clique : int
        number of clique of adjacent nodes
    n_ad : int
        number of adjacent nodes
    """
    def __init__(self, ad_set, n_pair, n_clique):
        self.ad_set = ad_set
        self.n_pair = n_pair
        self.n_clique = n_clique
        self.n_ad = len(ad_set)

    def add_ad(self, other, other_ad_set):
        """add adjacent node
        Parameters
        ----------
        other : any
            node-id
        other_ad_set : set
            set of other's adjacent nodes
        """
        self.n_ad += 1
        self.n_pair = self.n_ad * (self.n_ad - 1) // 2
        self.n_clique += len(self.ad_set & other_ad_set)
        self.ad_set.add(other)
    
    def score(self):
        """calculate clustering score
        
        Returns
        -------
        float
            clustering score, n_clique / n_pair
        """
        return self.n_clique / self.n_pair if self.n_pair > 0 else 0
    
    def __str__(self):
        return (
            f"n_pair {self.n_pair:2d},"
            +f" n_clique {self.n_clique:2d},"
            +f" n_ad {self.n_ad},"
            +f" ad_set {self.ad_set}"
        )

node_info = {
    # node-id       #ad_set n_pair n_clique
    i: AdjacentData(set(),  0,     0)
    for i in range(n_node)
}

## 閾値ごとに枝を追加 → クラスタ係数を更新

head = 0
tail = 0
n_all_pair = n_node * (n_node-1) // 2
for k in range(n_threashold):
    
    # get adding edge
    head = tail
    while tail < n_all_pair and sorted_pairs[tail].distance <= threasholds[k]:
        tail += 1
        
    # add edge & update node info
    for pair in sorted_pairs[head:tail]:
        G.add_edge(pair.first, pair.second)

        # u, v
        u, v = pair.first, pair.second
        node_info[u].add_ad(v, node_info[v].ad_set)
        node_info[v].add_ad(u, node_info[u].ad_set)

        # u - w - v
        for w in node_info[u].ad_set & node_info[v].ad_set:
            node_info[w].n_clique += 1

    # plot
    fig, ax = plt.subplots()
    nx.draw_networkx_edges (G, pos, edge_color='y', ax=ax)
    nx.draw_networkx_nodes (G, pos, node_color='r', alpha=0.5, ax=ax)
    nx.draw_networkx_labels(G, pos, font_size=10)
    title = f"round {k}, threashold {threasholds[k]}"
    for node in node_info:
        title += f"\nnode {node}, score {node_info[node].score():.4f} -- debug info {node_info[node]}"
    ax.set_title(title)