2014年C题outstanding奖

数学建模

matlab

5星 · 超过95%的资源需积分: 0 100 浏览量更新于2023-03-16 收藏 345KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

Who Is the Hidden Champion in a Network?

February 10, 2014

1 Summary

Network science is essential in many civil and military applications due to its great help

to complex systems with network-based structures. Since the co-author relationship as well as

the citation relationship forms a network structure in research areas, network science can be

utilized to do some data-mining works in this network, e.g. seeking inﬂuential researchers and

important research papers.

In this paper, we extract useful data from given large datasets and establish the required co-

author and citation networks. For visual clarity of the network, we propose and implement the

stress majorization algorithm based on the minimal-energy principle in physics, which provides

a proper 2-D layout for complex networks. Then we develop four different centrality measures

based on the perspectives of trivial sum, weighted sum, geographic control and informational

control, respectively, for undirected graph and three centrality measures for directed graph, in

which both the non-parametric and parametric methodologies are involved. Furthermore, we

propose several methods to transform a directed graph into an undirected one. We show that

these measures generate consistent results for both the most inﬂuential researcher and the most

important paper.

Then we extend our model from research areas to other areas of society, and show that our

model still yields convincing results for top singers, songwriters and movie stars, even when a

bipartite graph is used instead. Moreover, we conclude that a crude criterion for a real problem

to be solved by network science in essence is that there is a network structure and something

in interest transmitting through the network, with all real experiments conforming to this s-

tatement. In addition, it is proved theoretically and veriﬁed numerically that our parametric

approach guarantees its convergence, hence there are only loose requirements for parameters.

In summary, our model is practical and reliable for handling network-based problems in real-

ity. Nevertheless, there are some existing problems such as computational complexity and lack

of automatic adaptation preventing our model from convenient implementation, and certain

phenomenon such as information cascade lies beyond the scope of our modelling.

Key Words: network science, co-author, citation, centrality, stress majorization

Team # 30221 Page 2 of 20

Contents

1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Task 1: Co-author Network of the Erdos1 Author . . . . . . . . . . . . . . . . . . . . . . 3

4 Task 2: Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4.1 Degree Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4.2 Eigenvector Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4.3 Closeness Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.4 Betweenness Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.5 Summary of Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 Task 3: The Citation Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5.1 Undirected Graph Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.2 Directed Graph Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5.3 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

6 Task 4: Applications in Singers and Movie Actors . . . . . . . . . . . . . . . . . . . . . 13

6.1 Basic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6.2 Bipartite Graph Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7 Task 5: Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

8 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8.1 Non-parametric Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8.2 Parametric Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Strengths and Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9.1 Strengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9.2 Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Team # 30221 Page 3 of 20

2 Introduction

Network science has gained its popularity recently due to the considerable network struc-

tures emerging in reality, which can be of great help to data mining, dynamic systems, etc. In

academic ﬁelds, we can establish the corresponding network structures for both citation and co-

authoring relationships, and then the data mining work within these networks is of great interest

and signiﬁcance. Some simple questions are raised: how to measure the inﬂuence of a researcher, or

how to evaluate the importance of a research paper?

To answer this question, there are network-based evaluation tools that use co-author and

citation data to determine the impact factor of researchers, publications and journals, such as

Science Citation Index (SCI), H-factor, Impact factor, Eigenfactor, etc. Our goal is to design

effective measures to analyze inﬂuence in research networks, and then extend it to other areas

of society. Speciﬁcally, we will do the following things in this paper:

• Establish a co-author network using given data and plot it on a 2-D plane, then propose

several measures to determine who is the most inﬂuential researcher.

• Propose models to evaluate the importance of research papers using co-author and citation

data.

• Extend the models to other areas in society or other entities in research areas, then test and

analyze its performances.

• Gain heuristics from this model and discuss how individuals can learn from it in reality.

• Implement the sensitivity test and analyze its strengths and weaknesses, as well as the

potential research directions.

3 Task 1: Co-author Network of the Erdos1 Author

First of all, we build the co-author network of the Erdos1 authors from the source provid-

ed by the problem. Due to the symmetry of the pairwise co-author relationship, it is natural

to utilize graph theory to fully characterize it, where we establish a simple undirected graph and

regard researchers as vertices and the co-authoring relationship as edges. For computational sim-

plicity, we use an adjacency matrix A = (a

)

N×N

to store this relationship, where N = 511 is the

number of researchers who have co-authored with Erd

os, and the entry a

is an indicator of the

relationship:

(

1 researcher i has co-authored with researcher j

0 elsewhere

(1)

In particular, since this graph is undirected, A is symmetric.

Observing that the dataset is large (with 511 researchers and over 18,000 raw lines), we use

programming to accomplish data extraction. Speciﬁcally, we just write a simple string matching

algorithm by Ruby codes, which exports the corresponding adjacency matrix (excluding Erd

os)

for further use

. Once we obtain the adjacency matrix A, some of its properties such as transitiv-

ity ratio

are listed as follows.

Note that the resulting matrix is not symmetric due to some minor errors in source data, and we force its symmetry

by assigning a

← max(a

, a

The transitivity ratio describes how vertices tend to cluster and is deﬁned as

C ,

3 × number of triangles

number of connected triples of vertices

trace(A

)

sum(A

− A)

Team # 30221 Page 4 of 20

Table 1: Basic Properties for Co-authoring Relationship

Number of vertices Number of edges Average degree Transitivity ratio

511 1713 6.70 0.2238

Since the average degree 6.70  511, we observe that this graph is sparse. Moreover, accord-

ing to the transitivity ratio, this co-authoring relationship is moderately transitive. These results

meet our intuition that researchers often co-authored with those who they are familiar with, but

there are also some restrictions on pairwise cooperation, e.g. time limitation. To see deeper into

this graph, we summarize its degree distribution in Table 2.

Table 2: Degree Distribution

Range of degree 0 [1,2] [3,5] [6,10] [11,20] [21,30] [31,d

max

=52]

Number of vertices 37 150 122 114 51 23 14

As is illustrated in the table, majority of vertices have small degrees, while a fraction (16%)

of researchers are somewhat well-known who have co-authored with many researchers (more

than 10) in this list. This fact could also be illustrated by the network plotted on a 2-D plane,

while it is a challenging task owing to the obvious difﬁculties in designing a proper and visible

layout. It is quite complicated to deﬁne visible here, but intuitively, it is better to place two linked

vertices to be close, and place the distance of those which there is no edge connecting them to

be relatively far.

Using the heuristics above, Gansner et al.[1] developed a graph-drawing method called stress

majorization. Assume that there exists an optimal distance between each pair (this distance is set

according to certain criteria, such as the one discussed above), then we can approach this optimal

state by setting the vertices properly. We consider a metric to measure the so-called approaching

as follows.

stress(X) ,

i<j

(kX

− X

k − d

)

(2)

where X

∈ R

is the 2-D position for vertex i, d

, w

’s are optimal distances and corresponding

weights, respectively, and k · k is the Euclidean distance. [1] suggests:

• d

is the overall length of the shortest path connecting i and j (is computed using Floyd

Shortest-Path Algorithm[2]), with each edge (i, j) assigning a length

= #{k : exactly one of (k, i) and (k, j) is an edge} (3)

• w

= d

−2

is the corresponding weight.

We can imagine that there is a mechanic spring with equilibrium length d

and stiffness

coefﬁcient w

between each pair of vertices, then physical force will drive the system into a

state with minimal energy regardless of the initial state. This motivates us to use iterative methods,

where each iteration is an optimization step. Consider

F (X, Y ) ,

i<j

+ trace(X

LX) − 2 · trace(X

Y ) (4)

where

(

−w

i 6= j

k6=i

i = j

, L











0 i 6= j, Y

= Y

−d

/kY

− Y

k i 6= j, Y

6= Y

−

k6=i

i = j

(5)

剩余19页未读，继续阅读

Dchange

粉丝: 3
资源: 1

2014年C题outstanding奖

2014年数学建模美赛题目

2014年数学建模美赛题目原文及翻译.pdf

2014美国大学生数学建模大赛C题处理后数据

如何优化axi outstanding

ahb支持outstanding吗

什么是axi的outstanding

用SV写一个计算 AXI outstanding的checker

axi4 outstanding

fpga中outstanding

axi outstanding

axi outstanding如何实现

axi outstanding代码

用verilog写一个带有存储数据功能的axi-full slave模块,且该模块具备outstanding功能，outstanding大小为10

AXI outstanding传输时的时序图

axi总线的outstanding功能

AXI 协议中outstanding和burst的配合

用systemverilog写一个带有存储数据功能的axi-full slave,且带有outstanding功能，outstanding大小为10

axi的outstanding

AXI outstanding可以和burst一同生效吗

reordering_depth的值要小于outstanding值

最新资源