2014年美国大学生数学建模竞赛ICM(C题)一等奖

Team Control Number

For office use only

T1 ________________ T2 ________________ T3 ________________ T4 ________________

25072

Problem Chosen

c

For office use only

F1 ________________ F2 ________________ F3 ________________ F4 ________________

2014 Mathematical Contest in Modeling (MCM) Summary Sheet

Influence Model and Network Science

Network science is a new science and is widely used in modeling influence. In our paper, we develop two kinds of influence measures to solve undirected unweighted graph and directed weighted graph respectively.

For the first task, firstly we delete authors whose Erdos number is 2 and obtain the adjacency matrix. According to the adjacency matrix we draw the co-author network and remove isolated nodes of the network in order to limit the size of network. Then we analyze the properties of the network and the conclusions are as follows: this is a scale-free network since the network’s degree approximately obeys Power Law distribution; average clustering coefficient is 0.343; characteristic path length of network is about 3.825 and the diameter is10.

In the second task, considering the network is an undirected unweighted graph while PageRank algorithm is mainly used in directed graph, we establish the extended PageRank model taking nodes’ degree into account so as to optimize PageRank algorithm. The basic principle is to transfer node’s existing value to other nodes with cooperation relationship and it takes much iteration to converge. Finally we find HARARY FRANK with the highest PageRank value is the most crucial.

As for the third task, it is apparent that the citation network is a directed weighted graph, so we establish modified Markov Model and abstract a Markov chain out of the citation network to measure papers’ influence. Firstly we get adjacency matrix and weighing matrix according to the citation relationship. Secondly we are able to obtain the transition matrix from the adjacency and weighing matrix. Finally we get the stationary distribution and the most influential paper is “Collective dynamics of ‘small-world’ networks”.

When it comes to the fourth task, we establish an undirected and unweighted social network based on the data from Facebook and apply our first model to it. Finally we arrive at a conclusion that user ID25 has the strongest influence on the network.

At last, we conduct a sensitivity analysis to PageRank Model. We change damping factor to observe the changes of results on conclusion that it is more sensitive when damping factor d>0.5.

Key words: Network; Power Law; PageRank; Markov Chain; Erdos number