2015年亞太杯APMCM數(shù)學建模大賽

C題 識別網(wǎng)絡中的錯誤連接

原題再現(xiàn)

??網(wǎng)絡是描述真實系統(tǒng)結構的強大工具——社交網(wǎng)絡描述人與人之間的關系，萬維網(wǎng)描述網(wǎng)頁之間的超鏈接關系。隨著現(xiàn)代技術的發(fā)展，我們積累了越來越多的網(wǎng)絡數(shù)據(jù)，但這些數(shù)據(jù)部分不完整、不準確，有時甚至失真。例如，在生物網(wǎng)絡中，一些早期證明的現(xiàn)有基因-基因和蛋白質-蛋白質相互關系被更高精度的新實驗推翻。

??本主題將用6個網(wǎng)絡的數(shù)據(jù)來解決生物學、信息和社交網(wǎng)絡中的真實網(wǎng)絡問題。這些網(wǎng)絡的規(guī)模從數(shù)百個節(jié)點到數(shù)百萬個節(jié)點不等。每個網(wǎng)絡連接可能是無定向的（例如，推特中的朋友連接），也可能是定向的（如人們在推特中“關注”他人）。在原始真實網(wǎng)絡的基礎上，我們添加了一些符合以下標準的假連接：（1）假連接的數(shù)量不超過連接總數(shù)的10%；（2） 錯誤連接是以完全隨機的方式選取的。

??請閱讀附錄中的信息，并解決以下問題：

??（1） 開發(fā)一個數(shù)學模型來理解網(wǎng)絡的結構和組織機制。不同類型網(wǎng)絡的結構特征和組織原則并不總是相同的。

??（2） 提出了一種識別錯誤連接的有效方法。顯示如何發(fā)現(xiàn)結構特征的完整性；說明了數(shù)學模型的有效性和準確性以及算法的準確性。

??附件

??數(shù)據(jù)描述

??與該問題相關的網(wǎng)絡在表1中編號為1至6。補充信息中給出了數(shù)據(jù)本身及其如何獲得數(shù)據(jù)的詳細描述。

??對于上述網(wǎng)絡中的任何一個，如果錯誤連接的真實數(shù)量是R，則玩家應提交如何以標準格式識別這些R個錯誤連接（請參閱補充信息以了解提交的標準格式）。如果r個錯誤連接中的r個在提交中被正確識別，則得分為r/r。玩家在所有6個網(wǎng)絡中獲得的總分是衡量算法準確性的唯一指標。

整體求解過程概述(摘要)

??本文分析了復雜網(wǎng)絡的結構性質，研究了六種網(wǎng)絡中錯誤連接的識別問題。對于這些網(wǎng)絡，我們考慮了它們的拓撲結構，并進一步分析了一些特定的特性。

??首先，我們通過繪制網(wǎng)絡的視覺圖形來對它們進行視覺研究。經過分析，我們發(fā)現(xiàn)幾乎所有的網(wǎng)絡都存在小世界效應、大分支及其程度分布向右傾斜。生物定向網(wǎng)絡不服從冪律，其社會分化明顯。生物無向網(wǎng)絡和有向網(wǎng)絡除了服從冪律和具有協(xié)調性外，幾乎是一樣的。信息網(wǎng)絡的節(jié)點不具有模塊性，并且非常分散。兩個網(wǎng)絡都服從冪律和非關聯(lián)性。對于社交網(wǎng)絡，定向網(wǎng)絡服從冪律。無向網(wǎng)絡與有向網(wǎng)絡幾乎相同。然而，它并沒有巨大的分支。

??其次，我們發(fā)現(xiàn)生物定向網(wǎng)絡與食物鏈具有相似的特征，生物無定向網(wǎng)絡與生物器官相似。對于這兩種網(wǎng)絡，我們都使用入度和出度以及公共鄰居相似性來識別錯誤連接。結果表明，生物定向網(wǎng)絡的精度為0.364，無定向網(wǎng)絡的準確度為0.226。信息導向網(wǎng)絡類似于互聯(lián)網(wǎng)。我們使用了入度、出度和PageRank的排序來獲得錯誤連接。兩個信息網(wǎng)絡具有相同的特性。結果表明，信息定向網(wǎng)絡的精度為0.173，無定向網(wǎng)絡的準確度為0.309。對于社交導向網(wǎng)絡，我們認為它和推特有密切的關注模式。因此，我們假設“大V”節(jié)點和“活躍用戶”節(jié)點的存在。通過對其拓撲算法的分析，我們最終得出準確率為0.679的結果。對于社交無向網(wǎng)絡，我們認為它與twitter的好友添加模式具有相同的模式。我們使用相同的方法來處理它，最終結果是0.338。

模型假設：

??1.該錯誤不會影響每個網(wǎng)絡的真實鏈路拓撲特性。

??2.每個網(wǎng)絡的特異性都很低，大多數(shù)節(jié)點都遵循一定的規(guī)律性。

問題分析：

??本研究是現(xiàn)代社會的一個問題，隨著網(wǎng)絡的積累越來越多，我們如何應對日益龐大復雜的網(wǎng)絡數(shù)據(jù)分析。

??一個問題需要我們對不同的網(wǎng)絡體系結構模型分別進行分析，分析其結構和內部機制。首先，我們對數(shù)據(jù)進行分析，得出不同的網(wǎng)絡，如度分布、聚類系數(shù)、每個頂點的連接平均測地線距離等。利用這些數(shù)據(jù)，我們可以分析網(wǎng)絡的基本性質。然后我們利用這些數(shù)據(jù)，建立了每個網(wǎng)絡的隨機圖模型，通過分析和比較模型與原始網(wǎng)絡，了解每個網(wǎng)絡的不同結構。

??第二個問題要求我們提出一種有效的方法來識別六種不同網(wǎng)絡連接中的錯誤，并展示完整的結構特征，從中發(fā)現(xiàn)和解釋數(shù)學模型和算法的有效性和準確性。通過第一個問題我們已經知道了這些網(wǎng)絡拓撲的結構性質，網(wǎng)絡分別是有機體、生物無向網(wǎng)絡、信息有向網(wǎng)絡、無向網(wǎng)絡，社交網(wǎng)絡有別于社交網(wǎng)絡本身的無向結構特征的背離，做出了合理的分析，其中一些肯定會去除正確的鏈接，然后應用基于相似度的鏈接預測方法，建立共同的鄰居相似度指數(shù)，找出錯誤的鏈接。

模型的建立與求解整體論文縮略圖

文章來源地址http://www.zghlxwxcb.cn/news/detail-739510.html

全部論文及程序請見下方“ 只會建模 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:n
 C(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+1
 D=[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:N
 DeD(i)=sum(A(i,:));
end
aver_DeD=mean(DeD);
if sum(DeD)==0
 disp(' 該網(wǎng)絡只是由一些孤立點組成');
 return;
else
 figure;
bar([1:N],DeD); 
 xlabel('節(jié)點編號n');
 ylabel('?各節(jié)點度數(shù)K');
 title('網(wǎng)絡中各節(jié)點度數(shù)大小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('節(jié)點的度K');
ylabel('度為K的節(jié)點個數(shù)');
title('網(wǎng)絡中的節(jié)點度個數(shù)分布圖 ');
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 == len
 if num0(i)==check(i)
 i=i+1;
 
 else
 que_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;
 
 end
 
end
B2=B(:,2);
index=1:len;
reform_data=NaN*ones(len,len);
leak_std=1;
for j=index
 if j==leak(leak_std)
 leak_std=leak_std+1;
 continue;
 else
 judge_sign = (B1 == check(j));
 term=sum(judge_sign);
 reform_data(1:term,j)=B2(judge_sign);
 end
 
end
L=zeros(len);
S_xy=zeros(len);
AV_DeD=zeros(len);
for i=index
 for j=index
 Lx=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數(shù)學建模大賽C題識別網(wǎng)絡中的錯誤連接求解全過程文檔及程序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！