实现 networkx 中没有提供的 Weight Clustering 函数

NetworkX 功能补充

[TOC]

基于 NetworkX 的图结构和论文《The architecture of complex weighted networks》实现全局权重聚类系数的计算。

这个方法参考了 NetworkX 实现，比根据公式直接写快许多倍。

公式

NetworkX 中实现的全局权重聚类系数的是基于公式：
$$
\widetilde{C_i}=\frac{1}{k_i(k_i-1)}\sum_{j,k}(\hat{w_{ij}},\hat{w_{ij}},\hat{w_{ij}})^{1/3}a_{ij}a_{jk}a_{ik}
$$
而基于《The architecture of complex weighted networks》这篇论文中的公式：
$$
C_i^w=\frac{1}{s_i(k_i-1)}\sum_{j,h}\frac{w_{ij}+w_{ik}}{2}a_{ij}a_{jk}a_{ik}
$$
则没有被实现。因此我这里提供基于 NetworkX 的图结构的代码计算第二个公式：

代码

class MapUtil:
    @classmethod
    def add_value(cls, m, key, value):
        if key not in m:
            m[key] = 0
        m[key] += value
        
        
    @classmethod
    def add_number(cls, m, key):
        if key in m:
            m[key] += 1
        else:
            m[key] = 1
        
        
class NetworkXSupplement:
    """
    这个类用于提供论文 The architecture of complex weighted networks 中提到的计算权重聚类系数的方法。
    Networkx 原生提供的是另外一种。这个方法计算出的权重聚类系数和聚类系数。在图形上较为相似。
    """

    @classmethod
    def __imitate_the_change(cls, g, weight):
        nodes_nbrs = g.adj.items()

        strength_dict = {}
        for edge in g.edges():
            u = edge[0]
            v = edge[1]
            MapUtil.add_value(strength_dict, u, g[u][v].get(weight, 1))
            MapUtil.add_value(strength_dict, v, g[u][v].get(weight, 1))

        def add(m, v, nodes):
            if len(nodes) > 0:
                for n in nodes:
                    MapUtil.add_number(m, v)
                    MapUtil.add_number(m, n)

        for v, v_nbrs in nodes_nbrs:
            vs = set(v_nbrs) - {v}
            d = len(vs)
            if d == 0 or d == 1:
                yield (v, 0)
            else:
                edges_number_map = {}
                for w in vs:
                    nodes = vs & (set(g[w]) - {w})
                    add(edges_number_map, w, nodes)

                s = strength_dict[v]
                if s == 0:
                    yield (v, 0)
                else:
                    ans = sum(g[v][k].get(weight, 1) * val for k, val in edges_number_map.items()) / 2
                    yield (v, ans / (s * (d - 1)))

    @classmethod
    def clustering(cls, g, weight):
        td_iter = cls.__imitate_the_change(g, weight)
        clusterc = {v: cc for v, cc in td_iter}
        return clusterc

如何调用

例子1

import networkx as nx
g = nx.Graph()
g.add_edge(0,1,w=1)
g.add_edge(0,2,w=1)
g.add_edge(1,2,w=1)
print(NetworkXSupplement.clustering(g,'w'))

输出：

{0: 1.0, 1: 1.0, 2: 1.0}

例子2

import networkx as nx
g = nx.Graph()
g.add_edge(0,1,w=1)
g.add_edge(0,2,w=1)
g.add_edge(1,2,w=1)
g.add_edge(0,4,w=1)
g.add_edge(1,4,w=1)
g.add_edge(2,4,w=1)

g.add_edge(3,4,w=5)

print(NetworkXSupplement.clustering(g,'w'))

输出：

{0: 1.0, 1: 1.0, 2: 1.0, 4: 0.25, 3: 0}