构造随机网络并计算相关参数
使用C++手动构造一个随机网络并计算相关参数，然后使用python中的networkx进行绘制，随机网络为无向有权图，不具有实际的物理意义，但可以为构造实际的网络进行学习与参考。
使用无向有权图表示网络，图使用邻接表表示，维护一个节点列表，每个节点后跟着一个链表记录边，同时也使用三元组记录边便于记录参数
RandmNetWork.h
// Created by lsl on 2022/3/3. * 随机生成无向网络，节点与边都有权，使用int表示，允许自环 * 并没有实际的物理意义，但生成方法是一样的 * 使用领接表表示（节点，边）集合 class RandomNetwork { * 链表节点 struct ArcNode { int index; //节点 int weight; //边权重，表示链表首部节点a到该节点b的边a-b的权重 ArcNode *next; //下一个节点 * 领接表顶点（链表首个节点集合） * 还记录每个节点的统计信息 struct VNode { int index; //顶点（节点） int weight; //节点权重 int degree; //节点度值 double clusteringCoefficient; //集聚系数 ArcNode *first; public: * 边a-b struct ArcData { int head; //a int tail; //b int weight; //a-b边权重 bool operator==( const ArcData data) const { return head == data.head && tail == data.tail; int nodeCount = 10 ; //节点数量，0-nodeCount int arcCount = 10 ; //边数量,0-arcCount int weightScope = 10 ; //权重范围，0-weightScope //随机生成器 std ::random_device e; //权重随机器 std ::uniform_int_distribution< unsigned > wu; //节点随机器 std ::uniform_int_distribution< unsigned > au; //构造函数与析构 RandomNetwork( int nodeCount, int arcCount, int weightScope); ~RandomNetwork(); void Init () ; //初始化 void Display () ; //显示网络 std :: vector <VNode> getNodeInfo () ; //获取节点信息 * 一些统计函数 //度分布：度值为k的节点占整个网络中节点书的比例<k.pk>，度：节点连边的数量 std :: map < int , double > DegreeDistribution () ; //计算集聚系数，集聚系数Ci=2ei/(ki(ki-1)),ei表示节点i的邻居之间的边数，ki表示节点i的度 void ClusteringCoefficient () ; //计算度相关性，使用皮尔逊相关系数计算 double DegreeCorrelation () ; //导出数据，文件txt void ExportFile () ; private: std :: vector <VNode> vset; //顶点表 std :: vector < int > vsetVisited; //顶点访问标记数组 std :: vector <ArcData> arcDataList; //三元组记录边的信息 void _CreateVNodeSet(); //创建顶点集合 void _CreateRandomNetwork(); //创建随机无向网络 void _InsertArc(ArcData arcData); //插入边RandmNetWork.cpp
// Created by lsl on 2022/3/3. RandomNetwork:: RandomNetwork ( int nodeCount, int arcCount, int weightScope) { this ->nodeCount = nodeCount; this ->arcCount = arcCount; this ->weightScope = weightScope; wu = std:: uniform_int_distribution < unsigned >( 0 , weightScope - 1 ); au = std:: uniform_int_distribution < unsigned >( 0 , nodeCount - 1 ); RandomNetwork::~ RandomNetwork () { //释放内存，new申请的内存必须释放，在堆内 std::cout << "释放内存" << std::endl; for (VNode node: vset) { ArcNode *arcNode = node.first; ArcNode *tmp = arcNode; while (tmp != nullptr ) { arcNode = tmp; tmp = tmp->next; delete arcNode; * 创建顶点集合 void RandomNetwork::_CreateVNodeSet() { for ( int i = 0 ; i < nodeCount; i++) { //节点数据 ArcNode *arcNode = new ArcNode (); arcNode->index = i; //随机权重，简单随机 arcNode->weight = wu (e); arcNode->next = nullptr ; VNode node{}; node.index = i; node.weight = arcNode->weight; node.degree = 0 ; node.clusteringCoefficient = -1 ; node.first = arcNode; //加入集合 vset. push_back (node); * 插入边 void RandomNetwork::_InsertArc(RandomNetwork::ArcData arcData) { //按照index顺序创建顶点表，所以可以直接随机访问 ArcNode *first = vset[arcData.head].first; //链表第一个节点 ArcNode *tmp = first->next; //有边则不记录 while (tmp != nullptr ) { if (tmp->index == arcData.tail) { return ; first = tmp; tmp = tmp->next; //记录边 ArcNode *arcNode = new ArcNode (); arcNode->index = arcData.tail; arcNode->weight = arcData.weight; arcNode->next = nullptr ; //插入边 first->next = arcNode; //记录三元组，边的信息 if (std:: find (arcDataList. begin (), arcDataList. end (), arcData) == arcDataList. end ()) { arcDataList. push_back (arcData); //度值增加 if (arcData.head != arcData.tail) { vset[arcData.head].degree++; * 创建随机无向网络 void RandomNetwork::_CreateRandomNetwork() { if (vset. empty ()) { std::cout << "需要创建顶点集合" << std::endl; return ; for ( int i = 0 ; i < arcCount; ++i) { //随机生成边，简单随机 ArcData arcData{}; arcData.head = au (e); arcData.tail = au (e); arcData.weight = wu (e); _InsertArc(arcData); //需要注意会生成环，如果去掉环则去掉head==tail的数据即可 //插入边a-b，需要注意因为是无向图，所以还有边b-a if (arcData.head != arcData.tail) { ArcData another{}; another.head = arcData.tail; another.tail = arcData.head; another.weight = arcData.weight; _InsertArc(another); * 初始化网络 void RandomNetwork::Init () { _CreateVNodeSet(); //创建顶点集合 _CreateRandomNetwork(); //创建随机网络 * 显示网络 void RandomNetwork::Display () { for (VNode node: vset) { ArcNode *arcNode = node.first; while (arcNode != nullptr ) { std::cout << arcNode->index << "(" << arcNode->weight << ")->" ; arcNode = arcNode->next; std::cout << "null" << std::endl; * 获取节点信息，直接返回，ToDo 返回copy数据 * @return std::vector<RandomNetwork::VNode> RandomNetwork::getNodeInfo () { return vset; * 统计函数 * 度分布 * @return 度值为k的节点占整个网络中节点书的比例<k.pk> std::map< int , double > RandomNetwork::DegreeDistribution () { std::map< int , int > degreeMap; //<度值,度相同节点个数> std::map< int , double > m; for (VNode node: vset) { if (degreeMap. find (node.degree) == degreeMap. end ()) { degreeMap. insert (std:: make_pair (node.degree, 1 )); } else { degreeMap. find (node.degree)->second++; for (VNode node: vset) { if (m. find (node.degree) == m. end ()) { m. insert (std:: make_pair (node.degree, ( double ) degreeMap. find (node.degree)->second / nodeCount)); return m; * 集聚系数Ci=2ei/(ki(ki-1)),ei表示节点i的邻居之间的边数，ki表示节点i的度 void RandomNetwork::ClusteringCoefficient () { for ( auto &it : vset) { //度为0或1不进行计算 if (it.degree == 0 || it.degree == 1 ) continue ; //所有邻居 std::vector< int > neighbors; ArcNode *arcNode = it.first->next; while (arcNode != nullptr ) { //需要注意，环不是邻居 if (arcNode->index != it.index) { neighbors. push_back (arcNode->index); arcNode = arcNode->next; //计算邻居之间的边数，无向图，边会被重复计算，所以ei实际上就是2ei int ei = 0 ; if (neighbors. empty () || neighbors. size () < 2 ) { ei = 0 ; //邻居节点至少有两个才行 } else { for (ArcData arcData: arcDataList) { //去掉环 if (arcData.head == arcData.tail) continue ; if (std:: find (neighbors. begin (), neighbors. end (), arcData.head) != neighbors. end () && std:: find (neighbors. begin (), neighbors. end (), arcData.tail) != neighbors. end ()) { ei++; //计算集聚系数 double ci = ( double ) ei / it.degree / (it.degree - 1 ); it.clusteringCoefficient = ci; * 计算度相关性，使用皮尔逊相关系数计算 * @return 度相关性 double RandomNetwork::DegreeCorrelation () { //将所有连边的两端的度值按大小排列，分为两个集合x，y，计算度相关性 std::vector< int > x; std::vector< int > y; std::vector<ArcData> arcList; //不计算重复的边 ArcData check{}; for ( auto &it:arcDataList) { check.head = it.head; check.tail = it.tail; if (std:: find (arcList. begin (), arcList. end (), check) != arcList. end ()) { continue ; check.head = it.tail; check.tail = it.head; if (std:: find (arcList. begin (), arcList. end (), check) != arcList. end ()) { continue ; arcList. push_back (it); int a = vset[it.head].degree; int b = vset[it.tail].degree; x. push_back (std:: min (a, b)); y. push_back (std:: max (a, b)); //计算协方差Cov(x,y) double sum_multi = 0 ; double sum_x = 0 ; double sum_y = 0 ; for ( int i = 0 ; i < x. size (); i++) { sum_multi += (x[i] * y[i]); sum_x += x[i]; sum_y += y[i]; double e_xy = sum_multi / x. size (); double e_x = sum_x / x. size (); double e_y = sum_y / y. size (); double cov_xy = e_xy - (e_x * e_y); //计算标准差 double p_x = 0 ; double p_y = 0 ; for ( int i = 0 ; i < x. size (); i++) { p_x += std:: pow (x[i] - e_x, 2 ); p_y += std:: pow (y[i] - e_y, 2 ); double b_x = std:: sqrt (p_x / x. size ()); double b_y = std:: sqrt (p_y / y. size ()); return cov_xy / b_x / b_y; * 导出数据到文件 void RandomNetwork::ExportFile () { std::ofstream outfile; outfile. open ( "./nodes.txt" , std::ios::out | std::ios::trunc); //写入所有节点 outfile << "node" << std::endl; for ( auto node:vset) { outfile << node.index << std::endl; outfile. close (); //写入所有边 outfile. open ( "./edges.txt" , std::ios::out | std::ios::trunc); outfile << "head tail" << std::endl; for ( auto arc:arcDataList) { outfile << arc.head << " " << arc.tail << std::endl; outfile. close (); //写入度分布 outfile. open ( "./DegreeDistribution.txt" , std::ios::out | std::ios::trunc); outfile << "DegreeDistribution" << std::endl; for ( auto d: DegreeDistribution ()) { outfile << d.first << " " << d.second << std::endl; outfile. close (); //写入集聚系数 outfile. open ( "./ClusteringCoefficient.txt" , std::ios::out | std::ios::trunc); outfile << "ClusteringCoefficient" << std::endl; for ( auto node: getNodeInfo ()) { outfile << node.index << " " << node.clusteringCoefficient << std::endl; outfile. close ();main.cpp
#include <iostream>
#include "RandomNetwork.h"
#include "map"
using namespace std;
int main() {
cout << "输入节点数量>0（默认50）：" << endl;
int nodeCount = 0;
cin >> nodeCount;
nodeCount = nodeCount == 0 ? 50 : nodeCount;
int edgeCount = 0;
cout << "输入边的数量>0（默认100）：" << endl;
cin >> edgeCount;
edgeCount = edgeCount == 0 ? 100 : edgeCount;
//构造一个无向网络
RandomNetwork randomNetwork(nodeCount, edgeCount, 10);
randomNetwork.Init();
randomNetwork.Display();//节点（节点权重）->边（边权重)->边（边权重)...
//计算相关参数
std::cout << "网络度分布：度值：占据网络中节点的比例" << std::endl;
for (auto d: randomNetwork.DegreeDistribution()) {
std::cout << d.first << "：" << d.second << "，";
std::cout << std::endl;
std::cout << "集聚系数：节点：集聚系数（-1代表度值为0或1）" << std::endl;
randomNetwork.ClusteringCoefficient();
for (auto node: randomNetwork.getNodeInfo()) {
std::cout << node.index << "：" << node.clusteringCoefficient << "，";
std::cout << std::endl;
std::cout << "度相关性" << std::endl;
std::cout << randomNetwork.DegreeCorrelation() << std::endl;
//导出文件
randomNetwork.ExportFile();
cout<<"文件已导出";
system("pause");
return 0;
直接运行random_graph.exe生成nodes、edges、DegreeDistribution、ClusteringCoefficient四个文件记录信息并使用networkx绘制，方法说明：
Init()：初始化网络
Display()：显示网络
DegreeDistribution()：网络度分布
ClusteringCoefficient()：集聚系数
DegreeCorrelation()：度相关性
ExportFile()：导出信息到文件
使用 cmake与make生成random_network.exe，之后调用draw.py读取文件绘制图形，需要networkx、matplotlib、pandas三个库依赖
draw.py
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
nodes = pd.read_table("./nodes.txt")
edges = pd.read_table("./edges.txt")
deDis = pd.read_table("./DegreeDistribution.txt")
cluCoe = pd.read_table("./ClusteringCoefficient.txt")
G = nx.Graph()
# 添加节点
nodeList = []
for i in range(len(nodes)):
nodeList.append(nodes.iloc[i][0])
G.add_nodes_from(nodeList)
# 添加线
arcList = []
for i in range(len(edges)):
ns = edges.iloc[i][0]
edge = ns.split(' ', 2)
arcList.append((int(edge[0]), int(edge[1])))
G.add_edges_from(arcList)
# 绘制网络
plt.figure(figsize=(20, 20))
plt.subplot(2, 1, 1)
plt.title("network")
nx.draw(G, node_size=30, font_size=8)
# 度分布
de1 = []
de2 = []
for i in range(len(deDis)):
ns = deDis.iloc[i][0]
de = ns.split(' ', 2)
de1.append(int(de[0]))
de2.append(float(de[1]))
plt.subplot(2, 2, 3)
# 连通性
isolateNodes = list(nx.isolates(G))
isolateText = "isolate nodes:"
for i in range(len(isolateNodes)):
if i % 21 == 0: isolateText = isolateText + "\n";
isolateText = isolateText + str(isolateNodes[i]) + " "
plt.text(-0.2, 0.35, isolateText)
plt.title("degree-distribution")
plt.xlabel("degree")
plt.ylabel("k")
plt.bar(de1, de2, width=0.6)
# 集聚系数
cc1 = []
cc2 = []
for i in range(len(cluCoe)):
ns = cluCoe.iloc[i][0]
c = ns.split(' ', 2)
cc1.append(int(c[0]))
cc2.append(float(c[1]))
plt.subplot(2, 2, 4)
plt.title("clustering-coefficient")
plt.xlabel("node")
plt.ylabel("e")
plt.bar(cc1, cc2, width=0.6)
# 保存图片
plt.savefig("./ba.png")
plt.show()
效果图如下：
在python中可以直接使用networkx快速生成一个随机网络并计算相关属性，本次作业使用手动计算但之后可以使用networkx进行更方便的处理