搭建服务器做网站,手机在线编程网站,靖江seo收费贵吗,网站登录到wordpress复杂网络的任意子节点的网络最短距离
题目要求介绍 本文算法测试用的数据集为空手道俱乐部#xff0c;其中空手道俱乐部的数据集可通过这个链接进行下载•http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm#zachary
摘要
本文旨在解决复杂网络中任意子节点…复杂网络的任意子节点的网络最短距离
题目要求介绍 本文算法测试用的数据集为空手道俱乐部其中空手道俱乐部的数据集可通过这个链接进行下载•http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm#zachary
摘要
本文旨在解决复杂网络中任意子节点之间的网络最短距离问题。首先介绍了复杂网络的概念和特点包括小世界特性、无标度特性等。然后以空手道俱乐部网络为例展示了如何将邻接矩阵转换为邻接表并绘制网络图。接着设计了模块化的程序框架采用状态压缩动态规划 Dijkstra算法来计算任意m个节点之间的最短距离。最后给出了m2,3,4,5,5时的计算结果并以直方图形式可视化。结果表明在空手道俱乐部网络中大多数节点之间的最短距离分布在一个中等范围内说明大多数成员之间的社交关系维持在一个不亲不疏的状态。总体来说本文提出了一种有效的方法来分析复杂网络中节点之间的最短距离分布为研究复杂网络的拓扑结构提供了参考。
背景介绍
复杂网络Complex Networks是一种描述系统中元素间复杂连接关系的网络结构其特点在于节点数量庞大、连接关系复杂。复杂网络的研究涉及多个学科领域包括物理、数学、统计、计算机科学、社会学、生态学等。
复杂网络可概括为以下的部分
网络结构与演化机制复杂网络的结构具有小世界特性和无标度特性其演化机制包括随机连接、偏好连接、自组织临界等。网络拓扑性质与统计特性复杂网络具有高聚类系数、短平均路径长度等拓扑性质节点度分布呈现幂律分布等统计特性。网络动力学行为复杂网络中的节点和连接关系会影响网络的动力学行为如传染病传播、信息传播、社会动态等。网络中心性与节点重要性复杂网络中的节点重要性可以用网络中心性指标来描述如度中心性、介数中心性等。
在本例中我们着重于利用程序设计的图搜索算法来实现对空手道俱乐部的34个人构成的复杂人际关系网络进行处理通过用计算机进行模拟在此基础上可以分析出空手道俱乐部的人际关系
实验数据
初步给定的空手道俱乐部数据集中是一个邻接矩阵的形式
有权网络 无权网络 可以看到数据集中有非常多的0(黄色部分)这说明这个邻接矩阵是一个稀疏矩阵因此如果要提高程序运行的性能需要把这个矩阵转换成邻接表进行处理
首先将txt文件中的数字转换成python程序的二维list
然后将处理好的二维list转换成邻接表并写入到csv文件中 最终得到目标的数据集(部分)这个数据集就是后面程序直接进行处理的数据集
最后将这个csv文件的数据变成一个网络图片就能得到空手道俱乐部的人际网络
程序流程及系统设计
程序模块化构建
class Solution(object):#初始化参数def __init__(self,m0,NumberOfNode34,NumberOfEdge156) - 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,m0,NumberOfNode34,NumberOfEdge156) - 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**101), dtypeint) self.infinity 2 ** 24 self.p numpy.zeros(self.MaxNumberOfNode, dtypeint) 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, encodingutf-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,encodingutf-8) as file:linesfile.readlines()result[list(map(int, line.split())) for line in lines]return resultdef AdjMatrix_to_AdjList(matrix,Csv_filename空手道俱乐部.csv):with open(Csv_filename, w, newline,encodingutf-8) as file:writercsv.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([u1,v1,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:continuevis[u] Truefor 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_disheapq.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**101):self.dp[i][j] self.infinityfor i in range(1, self.m 1):self.dp[self.p[i]][1 (i - 1)] 0start 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.infinityfor 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]) , temptemp[:-2]self.results.append((temp, result, end - start))def save(self):csvfilepath csv结果/任意节点str(self.m).csvheaders [节点组合, 最短路径距离, 耗时]with open(csvfilepath, w, newline, encodingutf-8) as file:writer csv.writer(file)writer.writerow(headers)writer.writerows(self.results)def draw_network(self):list1[]with open(有权网络.csv,r,encodingutf-8) as file:readercsv.reader(file)list1[list(map(int,row)) for row in reader]graphnx.Graph()for i in range(len(list1)):graph.add_edge(list1[i][0],list1[i][1],weightlist1[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_colorblack, width1)edge_labels nx.get_edge_attributes(graph, weight)nx.draw_networkx_edge_labels(graph, pos, edge_labelsedge_labels)nx.draw(graph, with_labelsTrue)plt.savefig(图片结果/空手道俱乐部.png,dpi720)plt.show()def draw_bar(self):file_path 有权网络csv结果/任意节点str(self.m).csvshortest_path[]shortest_path_count{}with open(file_path,r,encodingutf-8) as file:readercsv.reader(file)shortest_path[row[1] for row in reader]shortest_pathlist(map(int,shortest_path[1:]))for length in shortest_path:shortest_path_count[length]shortest_path_count.get(length,0)1plt.rcParams[font.sans-serif] [SimHei]plt.rcParams[axes.unicode_minus] False plt.figure(figsize(10, 6)) plt.title(有权网络任意节点的最短路径长度) plt.xlabel(最短路径长度) plt.ylabel(频数) plt.grid(axisy, linestyle--, alpha0.7) plt.tight_layout() plt.bar(list(shortest_path_count.keys()), list(shortest_path_count.values()), alpha0.7, colorblue)bar_file_path 有权网络图片结果/任意节点str(self.m)直方图.pngplt.savefig(bar_file_path,dpi1080)
if __name____main__:for i in range(2,7):sSolution(mi) s.draw_bar()
