复杂网络的任意子节点的网络最短距离

题目要求介绍

本文算法测试用的数据集为空手道俱乐部，其中空手道俱乐部的数据集可通过这个链接进行下载•http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm#zachary

摘要

本文旨在解决复杂网络中任意子节点之间的网络最短距离问题。首先介绍了复杂网络的概念和特点，包括小世界特性、无标度特性等。然后以空手道俱乐部网络为例，展示了如何将邻接矩阵转换为邻接表，并绘制网络图。接着设计了模块化的程序框架，采用状态压缩动态规划 + Dijkstra算法来计算任意m个节点之间的最短距离。最后给出了m=2,3,4,5,>5时的计算结果，并以直方图形式可视化。结果表明，在空手道俱乐部网络中，大多数节点之间的最短距离分布在一个中等范围内，说明大多数成员之间的社交关系维持在一个不亲不疏的状态。总体来说，本文提出了一种有效的方法来分析复杂网络中节点之间的最短距离分布，为研究复杂网络的拓扑结构提供了参考。

背景介绍

复杂网络（Complex Networks）是一种描述系统中元素间复杂连接关系的网络结构，其特点在于节点数量庞大、连接关系复杂。复杂网络的研究涉及多个学科领域，包括物理、数学、统计、计算机科学、社会学、生态学等。

复杂网络可概括为以下的部分：

• 网络结构与演化机制：复杂网络的结构具有小世界特性和无标度特性，其演化机制包括随机连接、偏好连接、自组织临界等。
• 网络拓扑性质与统计特性：复杂网络具有高聚类系数、短平均路径长度等拓扑性质，节点度分布呈现幂律分布等统计特性。
• 网络动力学行为：复杂网络中的节点和连接关系会影响网络的动力学行为，如传染病传播、信息传播、社会动态等。
• 网络中心性与节点重要性：复杂网络中的节点重要性可以用网络中心性指标来描述，如度中心性、介数中心性等。

在本例中，我们着重于利用程序设计的图搜索算法，来实现对空手道俱乐部的34个人构成的复杂人际关系网络进行处理，通过用计算机进行模拟，在此基础上，可以分析出空手道俱乐部的人际关系

实验数据

初步给定的空手道俱乐部数据集中，是一个邻接矩阵的形式

有权网络

无权网络

可以看到，数据集中有非常多的0(黄色部分)，这说明这个邻接矩阵是一个稀疏矩阵，因此，如果要提高程序运行的性能，需要把这个矩阵转换成邻接表进行处理

首先将txt文件中的数字转换成python程序的二维list

然后将处理好的二维list，转换成邻接表并写入到csv文件中

最终得到目标的数据集(部分)，这个数据集就是后面程序直接进行处理的数据集

![img](https://raw.githubusercontent.com/kashima19960/img/master/%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C%E7%9A%84%E6%B1%82%E8%A7%A3%E6%96%B9%E6%B3%95/clip_image012.png)                                                                                                 ![img](https://raw.githubusercontent.com/kashima19960/img/master/%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C%E7%9A%84%E6%B1%82%E8%A7%A3%E6%96%B9%E6%B3%95/clip_image014.png)	注：一个有权，另一个无权

最后将这个csv文件的数据，变成一个网络图片，就能得到空手道俱乐部的人际网络

程序流程及系统设计

程序模块化构建

class Solution(object):
    #初始化参数
    def __init__(self,m=0,NumberOfNode=34,NumberOfEdge=156) -> None:
        pass
    #邻接矩阵转换
    def AdjMatrix_to_AdjList(matrix,Csv_filename):
        pass
    #图搜索算法
    def dijkstra(self, s) -> None:
        pass
    #核心算法
    def solution(self):
        pass
    #保存结果
    def save(self):
        pass
    #画出网状图
    def draw_network(self):
        pass
    #画出直方图
    def draw_bar(self):
        pass
#测试部分
if __name__=='__main__':
    pass

程序设计的具体细节

参数初始化

堆优化的dijstra算法

核心函数

函数的核心思想是状态压缩动态规划，通过枚举所有可能的m个节点的组合，计算每个组合的最短路径长度。Dijkstra算法用于辅助计算连接每个状态的最小距离。

初始化

• 使用numpy库生成一个包含所有节点的数组vertex。
• 使用combinations函数枚举所有可能的m个节点的组合。
• 初始化状态压缩DP数组self.dp，用于记录从每个节点出发，连接m个节点的最小距离。

状态压缩动态规划

• 对每个节点组合，初始化DP数组，将所有状态设为无穷大。
• 对于每个节点，将其连接到自身的状态设为0。
• 使用状态压缩动态规划，更新DP数组，计算从每个节点出发，连接m个节点的最小距离。

Dijkstra算法

• 对于每个状态，使用Dijkstra算法计算连接该状态下的m个节点的最小距离，并更新DP数组。
• Dijkstra算法通过优先队列实现，每次选择距离最小的节点进行扩展。

结果统计

• 统计所有节点组合的最短路径长度，并保存到results列表中。
• 对每个节点组合，找到最小路径长度和耗时。

输出结果

• results 列表包含了所有节点组合的最短路径长度

计算流程图

程序计算结果

X轴表示任意m的节点的最短路径的长度，Y轴表示任意m的节点的最短路径的长度出现的频数

4.1 m取值为2时，程序运行结果

有权网络

无权网络

4.2 m取值为3时，程序运行结果

有权网络

无权网络：

4.3 m取值为4时，程序运行结果

有权网络：

无权网络：

4.4 m取值为5时，程序运行结果

有权网络：

无权网络：

4.5 m >=5时，程序运行结果

有权网络：

无权网络

实验结论与分析

无权网络的权重分布只有0和1，很难看出分布规律。

有权网络的数据呈现出接近正态分布的形态，峰值集中在中间部分，然后向两侧逐渐减少，将最短路径长度映射到空手道俱乐部成员的人际网络关系中，我们可以得出结论：在空手道俱乐部中，社交关系非常亲密与非常疏远的成员是占少数的，大多数成员的社交关系都是维持在一个不亲不疏的状态中

附录

太长了不想看？👿，那就算了，下面是全部的代码，自己参悟吧😊😊

import numpy
import heapq
from collections import *
import csv
from itertools import combinations
import time
import matplotlib.pyplot as plt
import networkx as nx
class Solution(object):
    def __init__(self,m=0,NumberOfNode=34,NumberOfEdge=156) -> None:
        self.NumberOfNode = NumberOfNode  
        self.NumberOfEdge = NumberOfEdge  
        self.m = m  
        self.MaxNumberOfNode = self.NumberOfNode + 1  
        self.MaxNumberOfEdge = (self.NumberOfEdge + 1) * 2  
        self.dp = numpy.zeros((self.MaxNumberOfNode, 2**10+1), dtype=int)  
        self.infinity = 2 ** 24  
        self.p = numpy.zeros(self.MaxNumberOfNode, dtype=int)  
        self.AdjacencyList = {}  
        self.PriorityQueue = []  
        self.results=[]
        for i in range(1, self.MaxNumberOfNode):
            self.AdjacencyList[i] = {}
        Data = namedtuple('Data', 'source, target, weight')
        for edge in map(Data._make, csv.reader(open("无权网络.csv", encoding='utf-8'))):
            self.AdjacencyList[int(edge.source)][int(edge.target)] = int(edge.weight)
            self.AdjacencyList[int(edge.target)][int(edge.source)] = int(edge.weight)
    def txt_to_list(file_path):
        with open(file_path, 'r',encoding='utf-8') as file:
            lines=file.readlines()
            result=[list(map(int, line.split())) for line in lines]
        return result
    def AdjMatrix_to_AdjList(matrix,Csv_filename="空手道俱乐部.csv"):
        with open(Csv_filename, 'w', newline='',encoding='utf-8') as file:
            writer=csv.writer(file)
            writer.writerow(['source','target','weight'])
            for u in range(len(matrix)):
                for v in range(len(matrix)):
                    if matrix[u][v]!=0:
                        writer.writerow([u+1,v+1,matrix[u][v]])
        print(f"邻接矩阵已保存为CSV文件：{Csv_filename}")
    def dijkstra(self, s) -> None:
        vis = dict((key, False) for key in self.AdjacencyList)  
        while len(self.PriorityQueue) > 0:
            u, _ = heapq.heappop(self.PriorityQueue)  
            if vis[u] == True:
                continue
            vis[u] = True
            for v in self.AdjacencyList[u]:
                new_dis = self.dp[u][s] + self.AdjacencyList[u][v]
                if self.dp[v][s] > new_dis:
                    self.dp[v][s] = new_dis
                    heapq.heappush(self.PriorityQueue, [v, new_dis])
    def solution(self):
        vertex = numpy.arange(1, self.MaxNumberOfNode, 1)
        for tp in combinations(vertex, self.m):
            for i in range(1, self.m + 1):
                self.p[i] = tp[i - 1]
            for i in range(0, self.MaxNumberOfNode):
                for j in range(0, 2**10+1):
                    self.dp[i][j] = self.infinity
            for i in range(1, self.m + 1):
                self.dp[self.p[i]][1 << (i - 1)] = 0
            start = time.time()
            for s in range(1, 1 << self.m):
                for i in range(1, self.NumberOfNode + 1):
                    subs = s & (s - 1)
                    while subs != 0:
                        self.dp[i][s] = min(self.dp[i][s], self.dp[i][subs] + self.dp[i][s ^ subs])
                        subs = s & (subs - 1)
                    if self.dp[i][s] != self.infinity:
                        heapq.heappush(self.PriorityQueue, [i, self.dp[i][s]])
                self.dijkstra(s)
            end = time.time()
            result = self.infinity
            for i in range(1, self.m + 1):
                result = min(result, self.dp[self.p[i]][(1 << self.m) - 1])
            temp = ''
            for i in range(1, self.m + 1):
                if self.p[i]!=0:
                    temp += str(self.p[i])+' , '
            temp=temp[:-2]
            self.results.append((temp, result, end - start))
    def save(self):
        csvfilepath = 'csv结果/任意节点'+str(self.m)+'.csv'
        headers = ['节点组合', '最短路径距离', '耗时']
        with open(csvfilepath, 'w', newline='', encoding='utf-8') as file:
            writer = csv.writer(file)
            writer.writerow(headers)
            writer.writerows(self.results)
    def draw_network(self):
        list1=[]
        with open("有权网络.csv",'r',encoding='utf-8') as file:
            reader=csv.reader(file)
            list1=[list(map(int,row)) for row in reader]
        graph=nx.Graph()
        for i in range(len(list1)):
            graph.add_edge(list1[i][0],list1[i][1],weight=list1[i][2])
        pos = nx.spring_layout(graph)
        nx.draw_networkx_nodes(graph, pos)
        nx.draw_networkx_labels(graph, pos)
        nx.draw_networkx_edges(graph, pos, edge_color="black", width=1)
        edge_labels = nx.get_edge_attributes(graph, "weight")
        nx.draw_networkx_edge_labels(graph, pos, edge_labels=edge_labels)
        nx.draw(graph, with_labels=True)
        plt.savefig('图片结果/'+'空手道俱乐部.png',dpi=720)
        plt.show()
    def draw_bar(self):
        file_path = '有权网络csv结果/任意节点'+str(self.m)+'.csv'
        shortest_path=[]
        shortest_path_count={}
        with open(file_path,'r',encoding='utf-8') as file:
            reader=csv.reader(file)
            shortest_path=[row[1] for row in reader]
            shortest_path=list(map(int,shortest_path[1:]))
            for length in shortest_path:
                shortest_path_count[length]=shortest_path_count.get(length,0)+1
        plt.rcParams['font.sans-serif'] = ['SimHei']
        plt.rcParams['axes.unicode_minus'] = False  
        plt.figure(figsize=(10, 6))  
        plt.title('有权网络任意节点的最短路径长度')  
        plt.xlabel('最短路径长度')  
        plt.ylabel('频数')  
        plt.grid(axis='y', linestyle='--', alpha=0.7)  
        plt.tight_layout()  
        plt.bar(list(shortest_path_count.keys()), list(shortest_path_count.values()), alpha=0.7, color='blue')
        bar_file_path = '有权网络图片结果/任意节点'+str(self.m)+'直方图.png'
        plt.savefig(bar_file_path,dpi=1080)
if __name__=='__main__':
    for i in range(2,7):
        s=Solution(m=i)   
        s.draw_bar()