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

1 Introduction

Network science is an interdisciplinary academic field which studies complex networks [1]. One of the techniques to determine influence of academic research is to build a citation or co-author networks and analyze its properties. Erdos is the most famous academic co-authors on account of his over 500 co-author and over 1400 papers published. So it is of great significance to analyze the co-author data within Erdos1.

How to build the co-author network and develop influence measures to determine the most influential one? It requires us some skills for data extraction in order to remove the invalid data and limit the size of the network that we are going to research. Also, ability to analyze the properties of the network is needed so as to figure out the feature of the network. On one hand our goal is to establish a mathematics model to determine the most significant author. There is no need to consider Erdos since he will link to all nodes in Erdos1. On the other hand we are required to develop another different model to determine the most important works. Moreover, we will implement our algorithm on a completely different set of network influence data –for instance, influential songwriters, music bands, performers, movie actors, directors, movies, TV shows, columnists, journalists, newspapers, magazines, novelists, novels, bloggers, tweeters and so on.

Finally, we will discuss the science, understanding and utility of modeling influence and impact within networks and draw some conclusion. What’s more, we can also try to apply our model to the network of university, department, nation and society to demonstrate our models have good practicability and adaptability.

2 Assumptions

All the data given and found is valid and believable

We don’t take the people with Erdos number>1 or Erdos number=0 (being Erdos

himself) into account.

The timeline of cooperation can be neglected.

Neglecting the isolated node does not influence the accurate result.

3 Co-author Network

3.1 Analysis of Problem

In the Erdos1 file [2], there are over 18000 lines of raw data. According to the file we have known that these coauthors are listed one per line, single-spaced, each indented by a tab, last name first, in alphabetical order; those who have Erdos number 1 are in ALL CAPS, and those who have Erdos number 2 are in Normal Capitalization.[3]. We can build the co-author network of the Erdos1 authors by deleting Erdos number 2 authors. What’s more, we remove isolated nodes from the

network in order to limit the size of network. According to the network, we analyze these properties of network: degree distribution, clustering coefficient, characteristic path length and diameter of network.

3.2 Draw Co-author Network

After removing the Erdos number 2 authors in the Erdos1 file, we obtain the adjacency matrix. We use GEPHI [4] to build the co-author network based on the Erdos1 authors’ matrix and remove isolated nodes to get the 466*466 adjacency matrix. The network is as follows:

Figure 1: Co-author Network

In order to show the network better, we replace the na …… 此处隐藏：20657字，全部文档内容请下载后查看。喜欢就下载吧 ……