1.对于您生成的四个图形中的每个图形，计算图形的拉普拉斯算子的所有特征值和相应的特征向量（例如，使用MatLab（或Numpy）的eig

1个

CptS 591: Elements of Network Science Spring 2021

Assignment 2: Centrality and Ranking. Due by: Tue, Mar. 16, 2021, 11:59pm

There are three problems in this assignment.

For Problem 1, you will work with four real-world networks. Three of these are networks selected from Mark Newman’s collection of Network Data (http://www-personal.umich. edu/~mejn/netdata/). The networks in the collection are given certain descriptive names. The three networks chosen for this assignment are called: (1) Political blogs, (2) Neural network, and (3) Internet. Read the brief descriptions there so you get an idea for what the networks are modeling. The data sets are in GML format, which is a format the package igraph understands.

You are free to choose the fourth real-world network for Problem 1, but it is recommended to be a social or information network. Examples include a social network in a certain community/context (school, workplace, prison, etc ), a Facebook network, a twitter network, a who-calls-whom network, who-trusts-whom network, a citation network, etc.

For Problems 1 and 2, you are expected to use the software tool igraph. For some of the calculations and plots you may need to use Numpy (which is a package for scientific computing with Python), MatLab or a similar environment. Problem 3 does not require any software tool. It is an essay-type question based on reading a paper.

Your submission: will be one PDF file consisting of your solutions and an appendix describing your procedures (e.g. listing of Python/R/Matlab codes).

Problem 1 (45%). First, briefly describe the fourth real-world network you chose to work with for this problem and provide a URL to where it is located. For each of the four real-world networks you study, identify the node(s) in the network with the highest scores in terms of the following centrality measures: (i) Degree, (ii) Eccentricity, (iii) Closeness, (iv) Betweenness, (v) Katz index, (vi) PageRank, (vii) Kleinberg’s Authority score, and (viii) Kleinberg’s Hub score.

Try to find out in what way the nodes identified by these measures as the most important might be important in the network. Are there cases in which the different centrality measures identify the same node(s) as the most important? Discuss your results.

Problem 2 (45%). Generate two types of random graphs using igraph’s methods for the Erdos-Renyi and Barabasi-Albert (preferential attachment) models. (The Barabasi-Albert model is a simple stochastic algorithm that generates a scale-free graph, a graph with a Power-Law degree distribution.) Let the number of nodes in each case be 20. Choose the parameters in the two models such that the two graphs you generate have roughly the same number of edges. In the same fashion, generate another set of two graphs, this time with the number of nodes in each case being 40, instead of 20.

1. For each of the four graphs you generated, compute all eigenvalues and corresponding eigenvectors of the Laplacian of the graph (e.g. using MatLab’s (or Numpy’s) eig

1

function). Do not include the results of this computation in your submission, but you will need the result for the subsequent subproblems.

1. Complete the following table for each graph. (In case the graph you generated consists of more than one component, in populating the table, consider the largest connected component.)

Graph n m dmin dmax l D ccg λ2 λn

where n is the number of nodes; m is the number of edges; dmin is the minimum degree in the graph; dmax is the maximum degree in the graph; l is the average path length; D is the diameter; ccg is the global clustering coefficient; λ2 is the second smallest eigenvalue (the algebraic connectivity); and λn is the largest eigenvalue. Discuss the observations you make out of these data.

2. For this subproblem you will focus on the 20-nodes graphs in each of the two models. You will generate two figures, one for each model. In each figure, plot two quantities together: the eigenvector corresponding to the second-smallest eigenvalue (λ2) and the eigenvector corresponding to the largest eigenvalue (λn). In the plots, the x-axis would show vertex ids and the y-axis shows value of the eigenvector. Compare and contrast the plots of the two graphs, and discuss any observations you make.

Problem 3 (10%). Read the first four sections of the SIAM Review article “PageRank Beyond the Web” by David Gleich (note a copy of the article is posted on the course’s page on Canvas under the Module PageRank). From the very wide range of applications of PageRank discussed in section 4 of the article, pick three that you personally found most fascinating (or interesting) and tell me why. For each application you picked, a couple of sentences stating your reasons is adequate, but you are welcome to write a few more sentences, if you wish.

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司