自作関数の平均クラスタリング係数の違う場所を指摘してほしい

前提・実現したいこと

Pythonで勉強がてらクラスタリング係数を求めるプログラムを作成しています。
今後これを他の言語に移植していこうと考えているのでできるだけライブラリを使わずに作りたいと思っています。

http://www.orsj.or.jp/~wiki/wiki/index.php/クラスタ係数

上のサイトを頼りに組んでみましたが、その関数の出力結果がnetworkxの平均クラスタリング係数と違ってしまいます。

networkxのコードも読みましたが、自分には読めるほどの技術がありませんでした。

def Graph_clus_ave(df):

  name_dic={} #ここから下はグラフの隣接行列
  cnt=0;
  for index,row in df.iterrows(): #ここで名前に数値を振る。
    if((row["a"] in name_dic.keys())==False):
      name_dic[row["a"]]=cnt
      cnt+=1
    if((row["b"] in name_dic.keys())==False):  
      name_dic[row["b"]]=cnt
      cnt+=1    
  vec = [[0 for i in range(cnt)] for j in range(cnt)]
  for index,row in df.iterrows():
    vec[name_dic.get(row["a"])][name_dic.get(row["b"])]=1
    vec[name_dic.get(row["b"])][name_dic.get(row["a"])]=1
  clus=0#ここからクラスタリング係数を計算していきます。
  v=[sum(vec[i]) for i in range(cnt)]
  for i in range(cnt):
    clus_sum=0
    for j in range(cnt):
      if(vec[i][j]==1):
        for k in range(cnt):
          if(vec[i][k]==1 and  vec[j][k]==1):
            clus_sum+=1
    if(v[i]>1):
      clus+=clus_sum/(v[i]*(v[i]-1))
###２回カウントされるのでclus_sum/2だが、v[i]*(v[i]-1)/2の２と相殺される###
  return clus/cnt

どこをどのように直せばいいのかもわからない状況です。
みなさまのお力をお貸しください。
お願いします。

試したこと

nx.average_clustering(G,count_zeros=None)を試したが、やっぱり値は違かった。
コンプリートグラフではキチンと１を返してくれます。
しかし他の生成したグラフでは違う値だったので処理自体に問題があるのだと思います。
例：G= nx.fast_gnp_random_graph(6, 0.5)で生成したグラフ
networkx:0.5
自作関数：0.25
###補足
使用したデータセットは重複データあるデータセットでした。

a	b
Aさん	Bさん
Cさん	Dさん
Aさん	Cさん
Dさん	Aさん
...	...

みたいな感じです。

行動規範の内容に同意します

回答1件

ベストアンサー

#ここからクラスタリング係数を計算していきます 以降のコードに問題はないように思えます。
以下のコードはわかりやすいように一部変数名を変えてますが、コードは質問のものと一緒です。
1000個ランダムに生成したグラフの平均クラスタ数を計算し、networkx の average_clustering と一致することは確認しました。

もし試されたデータで値が違うのだとしたら、隣接行列を作成する部分等に原因があるのではないでしょうか。

python
1import networkx as nx
2import numpy as np
3
4def average_clustering(A):
5    """隣接行列 A で表されるグラフの平均クラスタを計算する。
6    """
7    num_nodes = len(A)  # ノードの数
8
9    # 各点の次数を計算する。
10    deg = [sum(A[i]) for i in range(num_nodes)]
11
12    total_cluster = 0  # 各点のクラスタ数の合計
13
14    # 各点のクラスタ係数を計算する。
15    for i in range(num_nodes):
16        # 点 i を含む三角形の数を数える。
17        num_triangles = 0
18        for j in range(num_nodes):
19            if A[i][j] == 1:
20                for k in range(num_nodes):
21                    if A[i][k] == 1 and A[j][k] == 1:
22                        num_triangles += 1
23
24        if deg[i] > 1:
25            total_cluster += num_triangles / (deg[i] * (deg[i] - 1))
26
27    return total_cluster / num_nodes  # 平均クラスタ係数
28
29for i in range(1000):
30    G = nx.fast_gnp_random_graph(6, 0.5, seed=i)
31
32    # networkx で計算した平均クラスタ係数
33    avg_cluster1 = nx.average_clustering(G)
34    
35    # 自作関数で計算した平均クラスタ係数
36    A = nx.to_numpy_array(G)  # 隣接行列を取得する。
37    avg_cluster2 = average_clustering(A)
38    
39    # 2つの関数の結果が一致するかどうか
40    assert np.isclose(avg_cluster1, avg_cluster2)
41