寻找最稠密子图问题

发表于 更新于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

最近实验室让看一篇论文，研究的是在社交网络中发现动态社区，整个大问题可以分成两个子问题，其中一个子问题就是寻找最稠密子图的问题

最稠密子图问题

给定一个静态图G = (V, E)，V是节点的集合，E是边的集合，W是V的一个子集

先讲下求密度的公式：

1
d(G) = 2*|E|/|V|

再给出几个概念：

1
2
E(W) = {(u,v) ∈ E | u,v ∈ W}
G(W) = (W, E(W))

最稠密子图问题便是找出一个V的子集W，使d(G(W))最大

算法思路

  1. 迭代删除度数最低的顶点，得到一系列子图
  2. 找到一系列子图当中密度最大的那个，将其节点和边作为解返回

代码如下, 可以自己设置顶点和边来进行测试:

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
import copy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

Nodes = pd.Series([[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],[1215.0,245.0],
          [1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],[420.0,555.0]],
          index = ['a','b','c','d','e','f','g','h','i','j'])
nodes = ['a','b','c','d','e','f','g','h','i','j'] # 节点集合
edges = [['a','c'], ['a','b'], ['b','c'], ['d','e'],['a','e'],['i','j'],['j','a'],['f','h'],['b','g']] # 边集合
subGraphs = [] # 用于记录每次迭代得到的子图的边
subNodes = [] # 用于记录每次迭代得到的子图的节点
scores = [] # 用于记录每次迭代得到的子图的密度

ax1 = plt.subplot2grid((1, 2), (0, 0), colspan = 1)
ax2 = plt.subplot2grid((1, 2), (0, 1), colspan = 1) # 划分出两个绘图区域，分别用ax1与ax2表示

for node in nodes:
	ax1.plot(Nodes[node][0], Nodes[node][1],'o')
for edge in edges:
	ax1.plot([Nodes[edge[0]][0], Nodes[edge[1]][0]], [Nodes[edge[0]][1],Nodes[edge[1]][1]], 'k')

def getDegree(): # 返回的是一个字典，每个节点与其度数相对应
	degrees = {}
	for node in nodes:
		degrees[node] = 0
	for edge in edges:
		degrees[edge[0]] = degrees.get(edge[0]) + 1
		degrees[edge[1]] = degrees.get(edge[1]) + 1
	return degrees

def findMinNode(degrees): # 返回度数最小的那个节点，如果度数最小的节点不止一个，返回哪个都没关系，因为是等价的
	minDegree = 100
	minNode = 'a'
	for node in nodes:
		if degrees[node] < minDegree:
			minDegree = degrees[node]
			minNode = node
	return minNode

def delMinNode(minNode): # 删除度数最小的节点，相应的边也会被删除
	nodes.remove(minNode)
	newEdges = copy.deepcopy(edges)
	for edge in newEdges:
		if minNode in edge:
			edges.remove(edge)

def getScore(): # 得到图的密度
	score = 2*len(edges)/len(nodes)
	return score

for i in range(len(nodes)):
	newEdges = copy.deepcopy(edges) # 使用深复制，这样newEdges与edges不会互相影响
	newNodes = copy.deepcopy(nodes) # 同上
	subGraphs.append(newEdges)
	subNodes.append(newNodes)
	scores.append(getScore())
	degrees = getDegree()
	minNode = findMinNode(degrees)
	delMinNode(minNode)

index = scores.index(max(scores))
print(scores)
print(max(scores)) # 输出最大密度

newEdges = subGraphs[index]
newNodes = subNodes[index]
print(newNodes) # 将最稠密子图的节点输出
print(newEdges) # 将最稠密子图的边输出

for node in newNodes:
	ax2.plot(Nodes[node][0], Nodes[node][1], 'o')
for edge in newEdges:
	ax2.plot([Nodes[edge[0]][0], Nodes[edge[1]][0]], [Nodes[edge[0]][1],Nodes[edge[1]][1]], 'k')

plt.show()