MATLAB复杂网络处理入门

write by ai

原文：CSDN 链接 `n最近一周花了一些时间在一个所谓的亚太数学建模竞赛上，其实自己主要有两点考虑，一是当做美赛之前的一个热身；二是自己刚刚接触MATLAB编程，希望能锻炼一下。

下面是题目：

Identifyingthe error connections in the network

The network is apowerful tool to describe the structure of a real system—— the socialnetwork describes the relationship between human beings, and the World Wide Webdescribes the hyperlink relationship between web pages. With the development ofmodern technology, we have accumulated more and more network data, but the datais partially incomplete, inaccurate or sometimes distorted. For example, in thebiological network, some early proved existing gene-gene and protein-protein interrelationsare overturned by new experiments with higher accuracy.

This topic willaddress real network problems from biology, information and social networks withdata of 6 networks. The scale of these networks is ranging from hundreds ofnodes to millions of nodes. Each network connection may be undirected (forexample, friend-connection in twitter), or directed (such as people “follow”others in twitter). Based on the original real network, we have added a numberof false connections which meet following criteria: (1) the number of the falseconnections is not more than 10% of the total number of connections; (2) theerror connections are picked in a completely random manner.

Please read the informationin the appendix and solve the following questions:

(1)Develop a mathematical model to understand the structure and organization mechanicsof the network. The structural characteristics of the different types ofnetworks and the organization principle are not always the same.

(2)Propose an effective method to identify the error connections. Show the completenessof how the structural characteristics are discovered; explain the validity andthe accuracy of the mathematical model as well as the accuracy of the algorithm.

Attachment

Data description

Thenetworks related to this problem are numbered 1 to 6 in Table 1. The dataitself and its detailed description of how it can be obtained are given in the .

Table 1：Briefdata description

No.	networks	Types	nodes	Total connections	Error connections
１	Social network	Undirected	50398	44268	2108
２	Social network	Directed	25440	1506389	71732
３		undirected	2186	10491	499
４	Bio-network	Directed	293	2263	107
５	Info-network	undirected	4554	5788	275
６	Info-network	Directed	2591	9093	433

Forany of the above network, if the real number of error connections is R, thenthe player should submit how those R error connections are identified in astandard format (please refer to Supplementaryinformation for the standard format of submission). If r out of R error connections are identified correctly in thesubmission, then the score is r/R. The total score obtained by the players inall 6 networks is the only measure of the accuracy of the algorithm.

http://www.pkbigdata.com/common/competition/150.html,and get the right to download data and submit the results after register withyour real name. In order to guarantee fairnessof this competition, all teams must register with their real names, and eachteam can only register once. Anyone(any team) who does not register in realname, or register more than one team names or maliciously affect theregistration of other teams, will be disqualified.When registering the www.pkbigdata.com,the register email must keep the sameas the registration on the www.saikr.com/apmcm.Besides, the team name on the pkbigdata.com is your team number, for example0001, 1100.

2）               Please notethat each team not only need to submit the final paper, but also must submitthe algorithm and the results. In the contest page entitled “identify theerror connections in the network”, the players can see a more detailedinstruction of the data and the submission format of the results. During thecontest, for each network, each team has no more than 10 chances to submit theresults of the algorithm. Players can obtain a real-time ranking of all theteams for the algorithm accuracy of each network and the total accuracy scoreof all 6 networks. Please submit the results with the right team name as the onein the registration platform. Although the submission of the algorithm resultsis not necessary in this contest, the results have a great impact on the finalresults of the competition.

3）               The scoredefined by r/R need show on the abstract of the final paper. The expert groupcan consider the score but not all. Novel ideas are more important.

Thefollowing two books published by Higher Education Press maybe helpful for theparticipants to understand the problem and design algorithms:“Network Science:An Introduction”(Wang xiaofan et al., 2012); “Link Prediction” (Lv Linyuan etal., 2013).

想到这个学期也对无标度网络和小世界网络有所接触，所以看到题目不知水深水浅也就选了。

主要介绍第一问的一些处理技巧：

数据是给出了一些数字组合，每个组合代表一个连接，以下部分数据：

CSDN_CODE_BLOCK_0_TOKEN 经过检查发现，这些数字竟然还有跳跃，所以第一步为了分析数据，我就先引入了一个Map,吧这些数字从小到大排序，然后用序号代替数字，这样这些数字就连续了。

代码实现

CSDN_CODE_BLOCK_1_TOKEN 在完成排序之后，需要根据原有的连接来确定新序号的连接CSDN_CODE_BLOCK_2_TOKEN 根据新生成的连接生成相应的邻接矩阵，然后通过graphallshortestpaths函数求出最短路径CSDN_CODE_BLOCK_3_TOKEN 根据最短路径确定平均路径，网络直径以及加权平均路径：CSDN_CODE_BLOCK_4_TOKEN 接触matlabBGL工具箱CSDN_CODE_BLOCK_5_TOKEN

统计度分布CSDN_CODE_BLOCK_6_TOKEN 画图CSDN_CODE_BLOCK_7_TOKEN 得到图形，还是有一定幂律分布的

最后，这些代码都相对简练，如果有看不懂的一定要把函数先单独提出来学习。

体会matlab矩阵编程简洁之美：参考学习MATLAB for循环优化三例

其实主要任务是找到错误节点，显然没有完成这个任务，原因有三：

1、低估了问题难度，以及高估了自己的能力；

2、复杂网络确实是个比较难的问题；

3、方向不明确，找了很多无用的资料。

不过也在这一个星期深深感受到复杂网络的有趣之处，今后有机会还会继续花时间研究这方面的问题。