代写program、代做Java/C++程序语言

日期：2025-04-07 09:21

Complex Networks Homework 1

Coupled centrality measures

1 Instructions

• Deadline: Monday 7th April, 9am.

• Marks: This homework is worth 50% of your coursework mark, that is 10%

of your final mark. Please note that you need to pass both you coursework

and your final exam to pass the course.

• Submission: Please submit your solutions as a PDF on QM+. Handwrit ten or typed solutions (e.g., LATEX) are both acceptable.

• Please read carefully the introduction as it contains essential information

to solve the problems.

2 Introduction

Consider a citation network: a directed network where nodes represent journal

articles. A link from article i to article j indicates that i cites j. Articles that

contain valuable information are helpful, but so are good review articles, which

allow to effectively identify valuable articles. Hence, in a citation network, two

types of articles can be considered important:

• Authorities: articles that contain valuable information, and are thus cited

in helpful review articles.

• Hubs: articles that cite many authorities, helping scientists to find them.

We define a pair of coupled centrality measures to identify important articles:

• The authority centrality xi of an article i is proportional to the sum of

the hub centralities of the articles citing i:

xi = α

X

j:j cites i

yj . (1)

• The hub centrality yi of an article i is proportional to the sum of the

authority centralities of the articles i cites:

yi = β

X

j:i cites j

xj . (2)

1

3 Questions

1. Let G be a citation network with n articles. Let x = (x1, x2, . . . , xn)

T

be the (column) vector of authority centralities of articles in G, and let

y = (y1, y2, . . . , yn)

T be the (column) vector of hub centralities of articles

in G. By using the definition of adjacency matrix A of G, rewrite equations

(1) and (2) in matrix form. [6 Marks]

2. Show that

AAT x = λx and A

T Ay = λy,

for a certain value of λ. Specify the value of λ. [6 Marks]

This allows to conclude that the authorities and hub centralities are given,

respectively, by the eigenvectors of AAT and AT A with the same eigenvalue.

3. Justify why the matrices AAT and AT A have the same set of eigenvalues.

[8 Marks]

We want all entries in x and y to be positive. This is possible by the Perron Frobenius theorem, which ensures that this is the case if we take λ to be the

largest (i.e., most positive) eigenvalue.

Let us look at a specific example. Consider the following network G, with 5

articles v1, v2, v3, v4, and v5:

4. Write down the adjacency matrix A of G. [3 Marks]

5. Compute the authority and hub centrality for each node/article. (Hint:

Compute either the hub centrality or the authority centrality by finding the

characteristic polynomial of an appropriate matrix, and then the eigenvec tor associated with the largest eigenvalue. Deduce the other centrality using

your answers for question 1. Note that the centralities are defined only up

to a constant). [12 Marks]

6. Interpret the centrality values you found in Question 5. Which nodes are

more important according to each measure? [6 Marks]

7. Which nodes are likely to be review articles? Which review article was

probably written first? Why? [3 Marks]

8. Explain why the eigenvector centrality would not be meaningful for this

network. [6 Marks]

2