图算法之中心性

更新于
中心性算法（centrality algorithm）用于理解图中特定节点的角色及其对网络的影响。

中心性算法（centrality algorithm）用于理解图中特定节点的角色及其对网络的影响。之所以有用，是因为这些算法能够识别最重要的节点，并帮助我们了解群体动态，例如可信度、可访问性、事物传播的速度以及群体之间的桥梁。尽管这些算法中有许多是为社交网路分析而发明的，但它们已经在各种行业和领域中得到了应用。

PageRank

从当前节点的邻居，和邻居的邻居评估当前节点的重要性。用来源于其传递链接的数量和质量的的排名来估计一个节点的影响力。虽然已经被Google普及，但它被广泛认为是检测任何网络中有影响力的节点的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import random

class pageRank:
    def __init__(self, nodes, matrix):
        self.nodes = nodes
        self.matrix = matrix

    def matrix_multi(self, A, B):
        # 两个矩阵相乘
        result = [[0] * len(B[0]) for i in range(len(A))]
        for i in range(len(A)):
            for j in range(len(B[0])):
                for k in range(len(B)):
                    result[i][j] += A[i][k] * B[k][j]
        return result

    def matrix_multiN(self, n, A):
        # 矩阵A的每个元素都乘以n
        result = [[1] * len(A[0]) for i in range(len(A))]
        for i in range(len(A)):
            for j in range(len(A[0])):
                result[i][j] = n * A[i][j]
        return result
    
    def matrix_add(self, A, B):
        # 两个矩阵相加
        if len(A[0]) != len(B[0]) and len(A) != len(B):
            return
        result = [[0] * len(A[0]) for i in range(len(A))]
        for i in range(len(A)):
            for j in range(len(A[0])):
                result[i][j] = A[i][j] + B[i][j]
        return result

    def tran_and_convert(self, A):
        # 根据邻接矩阵求转移概率矩阵并转向
        result = [[0] * len(A[0]) for i in range(len(A))]
        result_convert = [[0] * len(A[0]) for i in range(len(A))]
        for i in range(len(A)):
            for j in range(len(A[0])):
                result[i][j] = A[i][j] * 1.0 / sum(A[i])
        for i in range(len(result)):
            for j in range(len(result[0])):
                result_convert[i][j] = result[j][i]
        return result_convert

    def main(self):
        N = len(self.nodes)  # 顶点数量
        d = 0.85  # 阻尼因子为0.85
        delt = 0.00001  # 迭代控制变量

        e = []
        for i in range(N):
            e.append(1)
        New_P = []
        for i in range(N):
            New_P.append([random.random()])
        r = [[(1 - d) * i * 1 / N] for i in e]

        A = self.tran_and_convert(self.matrix)
        norm = 100
        while norm > delt:
            P = New_P
            New_P = self.matrix_add(r, self.matrix_multiN(d, self.matrix_multi(A, P)))  # P=(1-d)*e/n+d*M'P PageRank算法的核心
            norm = 0
            # 求解矩阵一阶范数
            for i in range(N):
                norm += abs(New_P[i][0] - P[i][0])
        print(New_P)

if __name__ == '__main__':
    nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

    matrix = [[0,  10,   0,   0,   0,  11,   0,   0,   0],
              [10,  0,  18,   0,   0,   0,  16,   0,  12],
              [0,  18,   0,  22,   0,   0,   0,   0,   8],
              [0,   0,  22,   0,  20,   0,   0,  16,  21],
              [0,   0,   0,  20,   0,  26,   7,  19,   0],
              [11,  0,   0,   0,  26,   0,  17,   0,   0],
              [0,  16,   0,   0,   7,  17,   0,  19,   0],
              [0,   0,   0,  16,  19,   0,  19,   0,   0],
              [0,  12,   8,  21,   0,   0,   0,   0,   0]]

    p = pageRank(nodes, matrix)
    p.main()

拓展阅读

0%