2014 美赛原题链接

前两篇论文被选入论文集，摘要和原论文稍有不同。

对比一下，修改后的更加简洁清晰。

Keep Right to Keep “Right”

Abstract

Our goal is a model to evaluate the performance of the keep-right-except- to-pass (KRETP) rule and other alternatives, by simulating the traffic flow on a freeway. We construct models to analyze five influencing factors. Then we integrate multiple criteria to judge the performance of nine rules using a fuzzy synthetic  evaluation (FSE).

Our basic model focuses on lane-changing behavior, an essential component of overtaking (passing).

We extend our model with a cellular automaton-based approach. We assume that the drivers will change the lane with a specific probability if trigger and safety conditions are satisfied. We simulate traffic flow on a long section of a freeway, controlling occupancy, varying the number of lanes, maximum speed limit, minimum speed limit, and signaling behavior.

In addition to KRETP, we examine four other rules by revising the laws governing the cells in the cellular automaton. Then we design five improved rules.

We choose flow rate and average speed as traffic flow criteria, sharp braking frequency as a safety criterion, and satisfaction and standard deviation of speed as experience criteria. Then we use a fuzzy synthetic evaluation technique to integrate these criteria to determine the performance of each rule. We find that in a light traffic, a partial-assigned-lane-and-keep-right rule performs the best, while in heavy traffic, a different-speed-limit-on-each-lane rule is preferred.

We change the probability of lane-changing to adjust our model to a country such as Great Britain.  Moreover, we also simulate a freeway fully controlled by an intelligent system.

Additionally, we refine our extended model by considering the on- and off-ramps. We adopt open boundary conditions and assume that the vehicles flowing in are Poisson-distributed.

Evaluation System for College Coaching Legends

Abstract

To evaluate the performance (evaluation grade) of a coach, we formulate metrics on five aspects: historical record, game gold content, playoff performance, honors and contribution to the sport. Moreover, each metric is subdivided into several secondary metrics, making for a three-tier hierarchical structure. Take playoff performance as an example: We collect post-season results (Sweet Sixteen, Final Four, etc.) each year from the NCAA official Website, from Wikimedia, and so on.

First, we use the Analytic Hierarchy Process (AHP) to determine the weight of each metric on a coach’s evaluation. Second, we use Fuzzy Synthetic Evaluation (FSE) to overcome the weakness of excessively subjective factors in AHP. The FSE model is based on data and generates a fuzzy matrix. After that, we apply the entropy method and linear weights to obtain the coaches’ evaluation grades.

To evaluate the accuracy of the two models, we define hit score to reflect the difference between our results and standard rankings from several authorities, such as ESPN and Sporting News. Take NCAA basketball as a case study, AHP receives a 78.8 hit score while FSE gets 81.8, which indicates that FSE performs better than AHP. Afterwards, we develop an Aggregation Model (AM) combining the two models based on hit score. The top 5 college basketball coaches, in order, are John Wooden, Mike Krzyzewski, Adolph Rupp, Dean Smith and Bob Knight.

The time horizon does make a difference. According to turning points in NCAA history, we divide the previous century into six periods with different time weights, which leads to changes in the rankings.

We apply our model to college women’s basketball only to find that gender does not matter.

The model proves to be effective in other sports. The ranking of college football coaches is: Bear Bryant, Knute Rockne, Tom Osborne, Joe Paterno, Bobby Bowden; and the top 5 coaches in college hockey are Bob Johnson, Red Berenson, Jack Parker, Jerry York, Ron Mason.

We conduct sensitivity analysis on FSE to find the best membership function and calculation rule, and also on the aggregation weight. We find that AM performs better than either AHP or FSE alone. As a creative use, we apply AM to pick the top 3 U.S. presidents: Abraham Lincoln, George Washington, Franklin D. Roosevelt.

We discuss the strengths and weaknesses of our model and present a nontechnical explanation of it.

Who are the 20%?

Abstract

The famous ‘80-20’ rule states that the 80% influence is caused by the 20% for many events. This principle also applies to the network science: only few nodes have a significant influence and impact to the whole net work. In our paper, A Relation Distance Model and an Authority-Popularity Evaluation Model are employed to measure of the 20% and analysis of its influence.

For requirement 1 & 2, we construct the undirected co-author network based on the 511 order relationship matrix. A Relation Distance Model is proposed on the basis of SNA technique. It combines three centrality indexes as a measure (Eigenvector centrality) which takes both degree and the influence of co-authors into consideration outputs a new rank. Validation of the model is discussed by comparing the two ranking of the top 15 authors in Erdos1 network, we find ALON, NOGA M. is the most influential person in the Erdos1 network. The degree distribution of the Erdos1 network is proved to approximately be power-law distribution, which indicates it is a scale-free network.

For requirement 3, an Authority-Popularity evaluation Model is established to analyze the depth and the width of the influence of nodes. An Authority Index is calculated by our Modified PageRank Algorithm (including two step:initialization and iteration) to measure the depth of impact. A Popularity Index is defined as citation per year to reflect the width of influence. A set of 24 papers citation directed network with weight added to nodes is constructed to implement the algorithm. The final ranking of the paper is obtained by combining Authority-Popularity Indexes. For requirement 4, a set of 15 actors’ co-star bidirectional network with co-star movie as links is constructed. The iteration process is refined as the weight added to links instead of nodes.

For requirement 5, we discuss two characteristics of scale-free network: Growth and Preferential attachment. The philosophy of dynamics of scale-free network is revealed as the ‘Matthew effect’. The prior method to boost influence is proposed: finding the shortest links to the most influential author. Cooperating with the 80% (more approachable relatively) with low closeness centrality step by step and finally co-author with the key figure in the field.

A sensitivity analysis is conducted to study the robustness of our algorithm to Damp Coefficient and the result shows a good stability. Strength and weakness of our models is also discussed.

The research of influence based on the characteristic of a network

Abstract

To find the influential nodes in the network, the key is the definition of “influential” **and how to measure the influence. In this paper, we use two kinds of metrics to measure the influence of coauthor network and citation network. In coauthor network, both the **Authority and Importance of the researchers are proposed to measure the influential of researcher. And the second one in citation network take the citation times, publication time and the position in the network into account.

For the evaluation of coauthor, we first construct a coauthor network with 511 vertices and 18000 edges and it is an undirected graph. Next, we use software UCInet to analyze the degree centrality, eigenvector centrality, closeness centrality and betweenness centrality of the network. Since there is no

evident transfer relationship in the coauthor network, we using Authority and Importance to measure the influence of a research. In detail, the Authority is correlated with the coauthoring times with Paul Erdos and the Importance is measured by eigenvector centrality. Finally, we rank the researchers whose

authority is larger than 2 according to their importance. And the top 5 most influential researchers are: RODL, VOJTECH; LOVASZ, LASZLO; GRAHAM, RONALD LEWIS; PACH, JANOS; BOLLOBAS, BELA. Finally, we search for some data through websites and verify these people are really influential.

For the evaluation of papers, we first compare the difference between the citation network and coauthor network. According to the characteristic of Directed Acyclic Graph(DAG)， we define a contribution coefficient and self-contribution coefficient by making an analogy with the energy transfer in the food chain. Considering the less-effectiveness of PageRank Algorithm and Hits Algorithm, we design an algorithm, which is effective in solving the DAG problem, to calculate the contribution coefficient. We find 3 most influential papers: Paper 14, Paper 4 and Paper 2 in the NetSciFoundation.pdf.

In the third part, we implement our model to analyze a corporation ownership network. We use the value of the company’s cash, stock, real estate, technical personnel, patent and relationships to define its value. And we use the proportion of stock to measure the control ability of parent company. Applying the model and algorithm of citation network, we find 15 influential companies. Then we find that 9 of them are in the top 20 of authoritative ranking, which verifies the rationality of our result.

Finally, we describe how we can utilize these influential models to do some socialized service, to aid in making decision on company acquisition and to carry out strategic attack.

（NO TITLE）

Abstract

The keep-right-except-to-pass rule is widely implemented all around the world, but it may not be an optimum one. We define five evaluation criteria to evaluate the performance of a traffic rule, namely, the average traffic speed, traffic flow, danger index, the over-speed-limit effect and the under-speed-limit effect. To analyze the “keep right” rule’s performance theoretically, we apply a state transition approach, which is similar to the Markov model, in light traffic situation. The result shows that all the cars will travel in the right lane at a low speed in the long term. In heavy traffic, we analyze its steady state and discover that cars will break the “keep right” rule because they cannot find a chance to return to the right lane after overtaking. To test the theoretical results, we build a simulation model based on the Cellular Automation (CA) to simulate the traffic system under a given traffic rule. The simulation results are consistent with what we have got through the state transition approach.

In order to seek a better traffic rule, we develop 3 new rules based on the old rule. Then we evaluate their performance together with the old rule respectively using our CA-based simulator. After calculating the values of our evaluation criteria, we employ the Analytic Hierarchy Process (AHP) method to obtain the best solution. We find that the best rule is the one which forbids cars from overtaking to achieve the best safety performance and highest traffic flow.

Finally, we discuss some further topics. The result is that we can apply our best solution to left-hand traffic countries by simply changing the orientation, and that the application of intelligent system will improve the performance of the ‘‘keep right” system in light traffic， but deteriorate it in heavy traffic. Results of the sensitivity analysis based on the CA simulator have shown the robustness of our conclusions.

Our suggestion for the public is that everyone should consciously avoid the overtaking behavior to realize a better traffic condition. Further studies should focus on more complex circumstances such as the six-lane freeway. With more precise data available, we can further test and improve our models.

Who Is the Hidden Champion in a Network?

Abstract

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 influential researchers and important research papers.

In this paper, we extract useful data from given large datasets and establish the required coauthor 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 influential 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 statement. In addition, it is proved theoretically and verified 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 reality. 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

A Three-dimensional Network Impact Analysis Model
Based on Centralizing, Connecting and Spreading Characteristics

Abstract

Last decade has witnessed a burst in the research of network impact analysis. However, most of the previous research focused on single factor or single algorithm to analyze the impact, which is insufficient for complex networks.

According to our observation and correlation analysis, we propose a characteristic classification method to systematically construct a three-dimension network impact analysis model. We establish the concept of centralizing characteristics, connecting characteristics and spreading characteristics, each of which consists of three sub-characteristics. Sub-characteristics include degree, eigenvector centrality, PageRank algorithm, betweenness centrality, clustering coefficient, node removal method, closeness centrality and two newly-proposed characteristics----spreading breadth index and spreading depth index both obtained from a submodel we design ourselves. Principal Component Analysis (PCA) is applied to obtain three one-dimension characteristic vector respectively. Finally a weighted sum of the three characteristic vectors is obtained to represent the impact measurement result for each node in the network.

Three datasets have been used for testing the rationality of the model and very promising performances have been measured. Additional efforts are made to extract the data, validate our model, visualize the network and discuss various utilities. In this way, we offer a rather comprehensive and reliable solution to this problem.

We strongly recommended our model because of its novel ideas, convincing analysis, exquisite visualization and promising performances.

Keywords

Network Impact Analysis; Centralizing Characteristics; Connecting Characteristics; Spreading Characteristics; Spreading Breadth Index; Spreading Depth Index; PCA.

Freeway Traffic Model Based on Cellular Automata and Monte-Carlo Method

Abstract

Based on Cellular Automata and Monte-Carlo method, we build a model to discuss the influence of the “Keep right except to pass” rule. First we break down the process of vehicle movement and establish corresponding sub-models, inflow model for car-generation, vehicle-following model for one vehicle following another, and overtaking model for one vehicle passing another.

Then we design rules to simulate the movement of vehicles in sub-models. We further discuss rules for our model to adapt to the keep-right situation, the unrestricted situation, and the situation where transportation is controlled by intelligent system. We also design a formula to evaluate the danger index of the road.

We simulate the traffic on two-lane freeway (two lanes per direction, four lanes in total), and three-lane freeway (three lanes per direction, six lanes in total) via computer and analyze the data. We record the average velocity, overtaking rate, road density and danger index and assess the performance of the keep-right rule by comparison with the unrestricted rule. We vary the upper speed limitations to analyze the sensitivity of the model and see the impacts of different upper speed limits. Left-hand traffic is also discussed.

Based on our analysis, we come up with a new rule combining the two existing rules (the keep-right rule and the unrestricted rule) for an intelligent system to achieve better performance.

“Dream Team” of College Coaches

Abstract

In order to estimate the excellence of different sports coaches and to give a ranking result, two distinct models are developed. The first model is a comprehensive evaluation method. And the second model is a ranking algorithm analogous to the Journal Influence Algorithm.

In the first model, we take into account a variety of metrics, and divide them into two categories: Objective Metrics and Subjective Metrics. In the Objective Metrics, we consider four factors, the number of wins, winning percentage, champions and final fours. All these factors have contributions to the excellence of a coach. We deem that the total number of games in a year could affect the number of wins, and the unevenness of team quality could affect the winning percentage. By employing statistical regression method to process collected data, we establish two functions of influence coefficient to eliminate the discrepancy caused by the two kinds of effect. In the Subjective Metrics: we consider two factors, media popularity and tenure. We employ Fuzzy Analysis Method to quantify these two subjective factors. We further incorporate Analytic Hierarchy Process (AHP) and Gray Relational Analysis Grade Method (GRAP) to determine the weight allocation to different metrics. The final ranking gives a comprehensive result by weighing results returned by these two methods. Using data from Sports Reference and other websites, the rankings in basketball, football and baseball accord with previous media commentaries.

In the second model, we deem that the excellence of a certain coach can be reflected from the media impact over the span of history and that the interactions between two coaches can reflect the disparity of skill level between them. We use search results returned by Google to quantify the impact of one coach on another. Based on the search results, we build a cross-reference matrix to represent relationships between coaches. In view that the different time periods that two coaches were in may largely affect the interaction between them, and the personal reputation may influence the number of search results, we develop a weight function of two variables to compensate the influence of time and to rule out the redundant information.

In consideration of the similarity between personal influence and journal influence, we refer to the Journal Influence Algorithm introduced by Eigenfactor and establish a new ranking algorithm. The basic idea of the algorithm is subtle: using weight function to modify the cross-reference matrix, and taking into consideration of individual influence, the algorithm gives an evaluation vector to rank different coaches. To test the validity of this algorithm, we apply the algorithm into basketball, football and baseball. The algorithm gives a result that is similar to the result obtained in the first model. The ranking also agrees with previous media commentaries. Furthermore, by slightly adjusting the coefficients, we can apply the algorithm into various sports.

Methods of Measuring Influence Using Network Model

Abstract

In this paper, we build the network model to measure the impact of researchers, papers and so on.

We first use the network model to evaluate the impact of researchers,considering researchers as the nodes, and using sides to describe collaboration among researchers. We then propose the concept of importance degree and influence degree. They are all the properties of nodes. Importance degree depicts a node’s own weight in the network, while influence degree estimates a node’s total influence that mutual impact among nodes is included. Based on the comprehensive consideration of the clustering coefficient and degree, we put forward a new idea to measure a node’s importance degree. Then combining with PageRank algorithm, we can evaluate the influence degree of every node in the network. We can find ALON, NOGA M is the most influential researcher. By analyzing the properties of nodes, we find that for a general researcher, she/he should extend its collaborative network as greatly as possible, especially partner researchers with high importance degree.

Second, imitating previous methodology, we build the model to evaluate the impact of papers. We conclude that factors determining a paper’s influence contain three indexes: the first author’s H-value, the journal’s Impact Factor and cited index which is the concept we define to depict the influence degree of a paper in the aspect of citation. Referring to the previous idea, we construct a new network reflecting citation relationship among papers, then we can obtain the cited index of every paper. After having collected the value of another two indexes, we use AHP to determine the weight of three factors, and finally evaluate the total influence of a paper successfully. We find that the paper Statistical mechanics of complex networks is most influential.

After that we view the other fields instead of the academic area to extend our model. We apply our network model measure Chinese movie stars’ influence. We select a greatly influential movie star to replace the status of Erdös, and construct the cooperating network among movie stars. Having obtained influence degree of stars, the ranking of influence of movie stars maintained a highly consistent with reality. This is proof that our model is feasible. Then we discuss our model’s application for academic, military and SNS fields roughly.

Finally, we make a sensitivity analysis for our model, and discuss the impact of the changing of nodes and the papers’ feedback of citation relationship on the results.

Through previous analysis, we can see that our model can be applied to many files, so it has a relatively high generalization.

The Keep-Right-Except-To-Pass Rule

Abstract

The keep-right-except-to-pass (KRETP) rule has been adopted by many countries around the world, but does this rule actually make our transportation system more efficient? This report aims to analyze this rule along with several other traffic regulations.

Using a discrete cellular-automaton (CA) model and a continuum model, we can simulate real-life traffic situation on freeways via the Monte Carlo method and PDE system respectively. Through comparison with other two traffic rules, we obtain the conclusion that the KRETP rule is rather effective.

First we define three parameters-—traffic flow, safety index and average energy consumption (AEC) to evaluate the performance of the KRETP rule under various vehicle density. By calculating the optimal maximum velocities during light and heavy traffic, we obtain the influence of under-posted and over-posted speed limits. We also assert that our model can be transferred in “left-most” countries with a simple change of orientation.

Then we introduce two other traffic rules—the “Slow-Cars-To-Right”(SCTR) rule and the “Free Driving & Free Overtaking” (FDFO) rule. By comparing these three rules in terms of our pre-defined parameters, we confirm KRETP rule’s superiority and provide strategic advice for future freeway construction.

Next, under the control of an intelligent system, a “median” optimization method is proposed to improve the overall quality of freeway transportation system. According to simulation result, our optimization method does improve the performance in terms of all three parameters.

Finally, we discuss upon several defects of our model that require further research.

Keywords: KRETP Rule, CA Model, Continuum Model, Monte Carlo Method, Traffic Flow, Safety Index, Average Energy Consumption (AEC), Optimization

Influence Measures in Networks

Abstract

Problem Clarification

In this paper, we build several networks, study their properties, and build models to measure players’ influence. Off-the-shelf measures like degree are not optimal for influence estimation, because they do not consider all aspects of the network. We seek to define more accurate measures based on previous research for various networks and explore their utility in real life.

Model Design

Conventional measures such as centrality usually neglect some aspects of networks, for example, the weights of edges. Stephen P. Borgatti (2006) introduces a cohesion measure called KPP-NEG, but the order of nodes is still ignored, which causes inaccuracy.

We combine the Shapley approach with the cohesion measure to obtain the Shapley value of each node, which represents its contribution to the whole networks cohesion. It involves weight, structure, and order of nodes at the same time, which makes it superior to both conventional measures and KPP-NEG. However, this new approach can’t be applied to directed networks.

Therefore, we use Pagerank algorithm derived from website networks to deal with directed networks like the citation network. But the basic method is not suitable for citation networks due to the differences between websites and papers and the limited network size. So we optimize it by adding a virtual node representing papers outside the network in two steps.The first is to adjust the weight of edges according to references. The second involves Times

Cited of the target paper.

For undirected networks, the Shapley value of Edros Network shows that the most influential co-author is ALON, NOGA M., which is different from that ranked by betweenness. The Shapley value implemented in the movie star network shows that the most influential star is Matt Damon, which is the same as that ranked by betweenness due to the relatively small size of the network.

For directed networks - the citation network of 16 papers provided, the most influential paper remains the same whether in the extensive network or not, which is No.14. But the ranks of some papers change with different versions of Pagerank method.

Sensitivity analysis suggests that ranks based on Shapley value is sensitive to sample size, while ranks based on Pagerank is not sensitive to damping factor.

(NO TITLE)

Abstract

Aimed to look for the “best all time college coach” for the previous century， we employ methods in grey and fuzzy fields to build an evaluation model and give out coach ranks in various sports fields by massive calculating. Meanwhile, effects of gender and time criterion on evaluation are also considered.

In order to simplify our model, we firstly adopt AHP to filter factors and determine seven most influential criterion, including coaching time, gender, etc. With the weight of each criteria worked out, the abstract problem is transferred to a mathematic one.

Based on AHP Model, two advanced models are proposed to rank college coaches. Grey Correlation Model considers the relevance among evaluation criterion and evaluates all coaches by calculating correlation degree with respect to reference data series. Fuzzy Comprehensive Model integrates empirical formulas and membership function to get the membership matrix, through which we can figure out scores of each coach. Comparing two results with current ranks, we find that grey model has slight advantages over fuzzy model.

Considering time line horizon’s impact on evaluating results, we augment our model by revising the weights and re-rank, based on membership function. According to the comparison between former rank and the one considering time line horizon, we conclude that it has fewer effects on the top 10 college coaches while has more effects on those ranked behind. The final rank table is as follows:

Keywords: AHP   Grey Correlation Model    Fuzzy Comprehensive Model   final rank