代写program、代做Java/C++程序语言
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