文章目錄
- 一、論文主體
- 二、複現代碼
- 2.1 算法大緻流程
- 2.2 Python代碼實作
- 三、匈牙利算法
- Reference
一、論文主體
論文題目：《Finding community structure in networks using the eigenvectors of matrices》
Leading eigenvector
這是Newman（一個學實體的大佬） (2006)提出的一種自上而下的分層社群發現算法。該算法的核心是定義了一個子產品度矩陣（modularity matrix）。最大化子產品度的過程可以展現在子產品度矩陣的特征值分解中，子產品度矩陣在社群發現中的作用類似于由圖拉普拉斯算子在圖劃分中發揮的作用。
（1）首先計算子產品度矩陣的最大正特征值所對應的特征向量，
（2）然後根據特征向量中元素的正負符号将節點分成兩個社群。
如果特征向量中的所有元素都具有相同的符号，則說明該網絡沒有底層的社群結構。該算法的複雜度為O((m+n)n)。
基礎知識回顧：
定義一（圖的鄰接矩陣）：
- 給定一個圖，其對應的鄰接矩陣被記為。表示存在從結點到的邊，反之表示不存在從結點到的邊。
- 在無向圖中，從結點到的邊存在，意味着從結點到的邊也存在。因而無向圖的鄰接矩陣是對稱的。
- 在無權圖中，各條邊的權重被認為是等價的，即認為各條邊的權重為。
-
對于有權圖，其對應的鄰接矩陣通常被記為，其中表示從結點到的邊的權重。若邊不存在時，邊的權重為。
一個無向無權圖的例子：
- 其鄰接矩陣為：
定義二（拉普拉斯矩陣，Laplacian Matrix）：
- 給定一個圖，其鄰接矩陣為，其拉普拉斯矩陣定義為，其中度矩陣。
定義三（對稱歸一化的拉普拉斯矩陣，Symmetric normalized Laplacian）：
- 給定一個圖，其鄰接矩陣為，其規範化的拉普拉斯矩陣定義為
二、複現代碼
舉個小栗子，給出如下的矩陣：
2.1 算法大緻流程
（0）算法開頭先輸入對應的鄰接矩陣：
Matrix = [[0,1,1,0,0],
[1,0,1,0,0],
[1,1,0,0,0],
[0,0,0,0,1],
[0,0,0,1,0]] （1）通過一個for循環求第i個結點對應的值：
（2）再求出P矩陣：
（3）
（4）求出B矩陣的特征值：
（5）對B矩陣對應的特征值進行大到小排序，找到最大的特征值
（6）求出（5）的 對應的特征向量
（7）利用匈牙利算法将大于0和小于0的數進行處理（好像不用匈牙利也行）
2.2 Python代碼實作
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 20 09:52:03 2021
@author: 86493
"""
import numpy as np
# 0.計算鄰接矩陣
Matrix = [[0,1,1,0,0],
[1,0,1,0,0],
[1,1,0,0,0],
[0,0,0,0,1],
[0,0,0,1,0]]
VertexNum = len(Matrix[0])
A = np.array(Matrix)
# 1.計算第i個結點對應的度數ki
K = [0] * 100
for i in range(VertexNum):
# print(i)
K[i] = A[i].sum()
print("第{0}個結點的度數為：".format(i),K[i])
# 列印每行的累加結果,盡量用format(比%好一丢丢)
TwoM = sum(K) # 計算所有結點的度數之和，即2m
print(TwoM)
# 2.計算P矩陣,記得先初始化
PMatrix = [[0 for i in range(VertexNum)] for i in range(VertexNum)]
for i in range(0, VertexNum):
for j in range(0, VertexNum):
PMatrix[i][j] = K[i] * K[j] / TwoM
# 3.B=A-P
B = A - PMatrix
# 4.計算B矩陣的特征值
EigValue, EigVector = np.linalg.eig(B)
# 5.對所有特征值進行排序
np.set_printoptions(suppress=True)
print("排序前的特征值為：\n", EigValue)
EigValue1 = EigValue.copy()
EigValue.sort()
# SortEigValue = EigValue.sort()
np.set_printoptions(suppress=True)
print("排序後的特征值為：\n", EigValue)
# 6.求得對應的特征向量
EndEigValue = EigValue[VertexNum - 1]
# 找到最大特征值所在的位置,并求對應的特征向量
for i in range(VertexNum):
if(EigValue1[i] == EndEigValue):
EndEigVector = EigVector[:, i]
break
print("最大的特征值為：\n", EndEigValue)
np.set_printoptions(suppress=True)
print("對應的特征向量為：\n", EndEigVector)
# 7.剛才特征向量的元素大于0歸為1，小于0歸為-1
lst1 = []
lst2 = []
for i in range(VertexNum):
if(EndEigVector[i] > 0):
EndEigVector[i] = 1
lst1.append(i)
elif(EndEigVector[i] < 0):
EndEigVector[i] = -1
lst2.append(i)
print("處理後的特征向量為：\n", EndEigVector)
print("第一個社群的元素：",lst1)
print("第二個社群的元素：",lst2) 用我們上面的栗子，可以得到如下的社群分解的結果如下，兩個社群也是符合事實的。注意在列印數值時預設是科學記數法的，可以使用
np.set_printoptions(suppress=True)
去掉。
具體方法：控制檔案中小數位數
np.set_printoptions(precision=3, suppress=True)
參數：
precision
: 保留幾位小數，後面不會補0
supress
: 對很大/小的數不使用科學計數法 (true)
formatter
: 強制格式化，後面會補0
第0個結點的度數為： 2
第1個結點的度數為： 2
第2個結點的度數為： 2
第3個結點的度數為： 1
第4個結點的度數為： 1
8
排序前的特征值為：
[ 1.25 -1. -0. -1. -1. ]
排序後的特征值為：
[-1. -1. -1. -0. 1.25]
最大的特征值為：
1.25
對應的特征向量為：
[-0.36514837 -0.36514837 -0.36514837 0.54772256 0.54772256]
處理後的特征向量為：
[-1. -1. -1. 1. 1.]
第一個社群的元素： [3, 4]
第二個社群的元素： [0, 1, 2] 三、匈牙利算法
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 20 16:02:41 2021
@author: 86493
"""
import numpy as np
from scipy.optimize import linear_sum_assignment
cost =np.array([[4,1,3],[2,0,5],[3,2,2]])
print(cost,'\n')
row_ind,col_ind=linear_sum_assignment(cost)
print(row_ind)
#開銷矩陣對應的行索引
print(col_ind)
#對應行索引的最優指派的列索引
print(cost[row_ind,col_ind])
#提取每個行索引的最優指派列索引所在的元素，形成數組
print(cost[row_ind,col_ind].sum())
#數組求和 輸出：[0 1 2][1 0 2] [1 2 2] 5 [[4,1,3],
[2,0,5],
[3,2,2]]