2015年亚太杯APMCM数学建模大赛C题识别网络中的错误连接求解全过程文档及程序

本文主要是介绍2015年亚太杯APMCM数学建模大赛C题识别网络中的错误连接求解全过程文档及程序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2015年亚太杯APMCM数学建模大赛

C题 识别网络中的错误连接

原题再现

  网络是描述真实系统结构的强大工具——社交网络描述人与人之间的关系,万维网描述网页之间的超链接关系。随着现代技术的发展,我们积累了越来越多的网络数据,但这些数据部分不完整、不准确,有时甚至失真。例如,在生物网络中,一些早期证明的现有基因-基因和蛋白质-蛋白质相互关系被更高精度的新实验推翻。

  本主题将用6个网络的数据来解决生物学、信息和社交网络中的真实网络问题。这些网络的规模从数百个节点到数百万个节点不等。每个网络连接可能是无定向的(例如,推特中的朋友连接),也可能是定向的(如人们在推特中“关注”他人)。在原始真实网络的基础上,我们添加了一些符合以下标准的假连接:(1)假连接的数量不超过连接总数的10%;(2) 错误连接是以完全随机的方式选取的。

  请阅读附录中的信息,并解决以下问题:

  (1) 开发一个数学模型来理解网络的结构和组织机制。不同类型网络的结构特征和组织原则并不总是相同的。

  (2) 提出了一种识别错误连接的有效方法。显示如何发现结构特征的完整性;说明了数学模型的有效性和准确性以及算法的准确性。

  附件

  数据描述

  与该问题相关的网络在表1中编号为1至6。补充信息中给出了数据本身及其如何获得数据的详细描述。

在这里插入图片描述
  对于上述网络中的任何一个,如果错误连接的真实数量是R,则玩家应提交如何以标准格式识别这些R个错误连接(请参阅补充信息以了解提交的标准格式)。如果r个错误连接中的r个在提交中被正确识别,则得分为r/r。玩家在所有6个网络中获得的总分是衡量算法准确性的唯一指标。

整体求解过程概述(摘要)

  本文分析了复杂网络的结构性质,研究了六种网络中错误连接的识别问题。对于这些网络,我们考虑了它们的拓扑结构,并进一步分析了一些特定的特性。

  首先,我们通过绘制网络的视觉图形来对它们进行视觉研究。经过分析,我们发现几乎所有的网络都存在小世界效应、大分支及其程度分布向右倾斜。生物定向网络不服从幂律,其社会分化明显。生物无向网络和有向网络除了服从幂律和具有协调性外,几乎是一样的。信息网络的节点不具有模块性,并且非常分散。两个网络都服从幂律和非关联性。对于社交网络,定向网络服从幂律。无向网络与有向网络几乎相同。然而,它并没有巨大的分支。

  其次,我们发现生物定向网络与食物链具有相似的特征,生物无定向网络与生物器官相似。对于这两种网络,我们都使用入度和出度以及公共邻居相似性来识别错误连接。结果表明,生物定向网络的精度为0.364,无定向网络的准确度为0.226。信息导向网络类似于互联网。我们使用了入度、出度和PageRank的排序来获得错误连接。两个信息网络具有相同的特性。结果表明,信息定向网络的精度为0.173,无定向网络的准确度为0.309。对于社交导向网络,我们认为它和推特有密切的关注模式。因此,我们假设“大V”节点和“活跃用户”节点的存在。通过对其拓扑算法的分析,我们最终得出准确率为0.679的结果。对于社交无向网络,我们认为它与twitter的好友添加模式具有相同的模式。我们使用相同的方法来处理它,最终结果是0.338。

模型假设:

  1.该错误不会影响每个网络的真实链路拓扑特性。

  2.每个网络的特异性都很低,大多数节点都遵循一定的规律性。

问题分析:

  本研究是现代社会的一个问题,随着网络的积累越来越多,我们如何应对日益庞大复杂的网络数据分析。

  一个问题需要我们对不同的网络体系结构模型分别进行分析,分析其结构和内部机制。首先,我们对数据进行分析,得出不同的网络,如度分布、聚类系数、每个顶点的连接平均测地线距离等。利用这些数据,我们可以分析网络的基本性质。然后我们利用这些数据,建立了每个网络的随机图模型,通过分析和比较模型与原始网络,了解每个网络的不同结构。

  第二个问题要求我们提出一种有效的方法来识别六种不同网络连接中的错误,并展示完整的结构特征,从中发现和解释数学模型和算法的有效性和准确性。通过第一个问题我们已经知道了这些网络拓扑的结构性质,网络分别是有机体、生物无向网络、信息有向网络、无向网络,社交网络有别于社交网络本身的无向结构特征的背离,做出了合理的分析,其中一些肯定会去除正确的链接,然后应用基于相似度的链接预测方法,建立共同的邻居相似度指数,找出错误的链接。

模型的建立与求解整体论文缩略图

在这里插入图片描述
在这里插入图片描述

全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码:

部分程序如下:
clear;clc;close
A=load('InfoUD.mat');
P=100;
B=[];
B(:,1)=A.node1;
B(:,2)=A.node2;
if ~all(all(B(:,1:2)));B(:,1:2)=B(:,1:2)+1;
end
num=max(max(B));
C=zeros(num);
n=length(B);
for i=1:nC(B(i,1),B(i,2))=C(B(i,1),B(i,2))+1;
end
C=C+C';
R=get_degree_correlation(C);
[M,N_DeD,N_predict,DeD,aver_DeD]=Degree_Distribution(C,P);
N_predict=floor(N_predict);
j=sum(N_predict);
D=[];
for k=1:P+1D=[D (k-1)*ones(1,N_predict(k))];
end
function [ out ] = get_degree(A,k)
row = A(k,:);
out=size(find(row==1),2);
end
function [M,N_DeD,N_predict,DeD,aver_DeD]=Degree_Distribution(A,P)
N=size(A,2);
DeD=zeros(1,N);
for i=1:NDeD(i)=sum(A(i,:));
end
aver_DeD=mean(DeD);
if sum(DeD)==0disp(' 该网络只是由一些孤立点组成');return;
elsefigure;
bar([1:N],DeD); xlabel('节点编号n');ylabel('¸各节点度数K');title('网络中各节点度数大小K的分布图');
end
figure;
M=max(DeD);
predict=0:P;
for i=1:M+1; N_DeD(i)=length(find(DeD==i-1));
end
P_DeD=zeros(1,M+1);
P_DeD(:)=N_DeD(:);
bar([0:M],P_DeD,'r');
xlabel('节点的度K');
ylabel('度为K的节点个数');
title('网络中的节点度个数分布图 ');
hold on
N_predict=interp1([0:M],N_DeD,predict,'spline');
plot(predict,N_predict);
hold off
figure;
PK_DeD=zeros(1,M+1);
PK_DeD(:)=N_DeD(:)./sum(N_DeD);
bar([0:M],PK_DeD);
set(gca,'yscale','log','xscale','log');
xlabel('度k');
ylabel('度为k的顶点所占比例');
title('幂律度分布')
function [ r ] = get_degree_correlation( A)
B = triu(A);
M = size(find(B==1),1);
sum1=0;
sum2=0;
sum3=0;
A1 = find(B==1);
length = size(A1,1);
for i=1:length[x y]=ind2sub(size(B),A1(i));sum1 = sum1+get_degree(A,x)*get_degree(A,y);sum2 = sum2+get_degree(A,x)+get_degree(A,y);sum3 = sum3+get_degree(A,x)^2+get_degree(A,y)^2;end
x1 = sum1/M-(sum2/(2*M))^2;
y1 = sum3/(2*M)-(sum2/(2*M))^2;
r=x1/y1;
end
clear;clc;close
A=load('InfoUD.mat');
P=100;
B=[];
B(:,1)=[A.node1;A.node2];
B(:,2)=[A.node2;A.node1];
load('InfoUD_DeD.mat')
B1=B(:,1);
num0=unique(B1);
mini=min(num0);
maxi=max(num0);
check=mini:maxi;
len=length(check);
i=1;
leak_num=0;
leak=NaN*ones(len);
while i == lenif num0(i)==check(i)i=i+1;elseque_num=num0(i)-check(i);std_num=leak_num;final_num=que_num+leak_num;leak(std_num+1:final_num)=i:i+que_num-1;i=i+que_num;endend
B2=B(:,2);
index=1:len;
reform_data=NaN*ones(len,len);
leak_std=1;
for j=indexif j==leak(leak_std)leak_std=leak_std+1;continue;elsejudge_sign = (B1 == check(j));term=sum(judge_sign);reform_data(1:term,j)=B2(judge_sign);endend
L=zeros(len);
S_xy=zeros(len);
AV_DeD=zeros(len);
for i=indexfor j=indexLx=reform_data(:,i);Ly=reform_data(:,j);Lx=Lx(~isnan(Lx));Ly=Ly(~isnan(Ly));L(i,j)=length((intersect(Lx,Ly))); AV_DeD(i,j)=DeD(i)+DeD(j);S_xy(i,j)=2*L(i,j)/(DeD(i)+DeD(j));end
end
clear;clc;
A=load('S_xy_BU.mat');
UA=load('BioD.mat');
UVA=load('AV_DeD_BioUD.mat');
len1=length(UA.node1);
%C=load('C.mat');
C=zeros(len1,4);
%len1=length(C.C);
D=zeros(len1,4);
C(:,1)=UA.node1;
C(:,2)=UA.node2;
len=length(A.S_xy);
index=1:len;
B=zeros(sum(index),4);
i=1;
k=1;
while i<len+1 B(k:k+len-i,1)=i*ones(len+1-i,1);B(k:k+len-i,2)=i:len;
B(k:k+len-i,3)=A.S_xy(i,i:len);B(k:k+len-i,4)=UVA.AV_DeD(i,i:len);k=k+1+len-i;i=i+1;
end
B(:,1:2)=B(:,1:2)-1;
[B1 B2]=find(isnan(B));
B(B1,:)=[];
len2=length(B);
全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可

这篇关于2015年亚太杯APMCM数学建模大赛C题识别网络中的错误连接求解全过程文档及程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/336767

相关文章

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依