02 Tutorial Week3

INFS7450 SOCIAL MEDIA ANALYTICS
Tutorial Week 3
Liang QU
School of ITEE
The University of Queensland
Outlines
• Quiz 1 Answers
• Lecture Knowledge Extension
• Coding Demo
• Implementation of Node Centrality Measures
• Q&A
Section 1: Quiz 1 Answers
d
Section 2: Lecture Knowledge Extension
Section 2:
1. In-class Quiz about three geometric centrality measures
2. What are eigenvectors and eigenvalues?
3. How to calculate eigenvectors and eigenvalues?
In-Class Quiz (5 mins)
• Consider an undirected graph with 5 nodes (A,B,C,D,E) with the
following edge list:
(A,B)
(A,C)
(B,C)
(B,D)
(C,E)
Please calculate the centrality of nodes A and E using Degree Centrality,
Closeness Centrality, and normalized Harmonic Centrality methods,
respectively.
In-class quizzes will NOT be included in the final grade.
In-Class Quiz
Consider an undirected graph with 5 nodes (A,B,C,D,E) with the
following edge list:
(A,B)
E A B D
(A,C)
(B,C)
(B,D) C
(C,E)
Please calculate the centrality of nodes A and E using
Degree Centrality (DC), Closeness Centrality (CC), and
normalized Harmonic Centrality (HC) methods,
respectively.
DC CC Normalized HC
Node A 2 1 1 1 1 1 1 1 3
= = 0.17 + + + = = 0.75
1+1+2+2 6 4 1 1 2 2 4
Node E 1 1 1 1 1 1 1 1 7
= = 0.125 + + + = = 0.58
2+2+1+3 8 4 2 2 1 3 12
Section 2: Spectral Graph
Why we call those as spectral

methods? What’s the word
“spectral” means?
Section 2: Spectral Graph
Ø What is spectral?
Ø “Spectral” can be understood that it simply means decomposing a signal/audio/image/graph
into a combination (usually, a sum) of simple elements (wavelets, graphlets).
Ø Such decomposing generally has some nice properties, for example, these simple elements are
usually orthogonal, i.e., mutually linearly independent, and therefore form a basis.
Ø Spectral graph theory is the powerful and beautiful theory that arise from the following
question:
Ø What properties of a graph are exposed/revealed if we
1) Represent the graph as a matrix
2) Study the eigenvectors/eigenvalues of that matrix.
Ø We will begin with the very basic observation that graphs can be represented as matrices, and
then ask “what happens if we apply the linear algebraic tools to these matrices?”
Ø How to calculate the eigenvalues and eigenvectors of a matrix?
Spectral Graph Theory:

https://web.stanford.edu/class/cs168/l/l11.pdf
Section 2: Eigenvectors and Eigenvalues
Here, an interesting fact is that we multiply a matrix by a vector and get the same result as when we multiply
a scalar (just a number) by that vector.
Geometric interpretation of an eigenvector:
When we multiply matrix A by the eigenvector, the direction of
the eigenvector remains unchanged.
Recall 𝐵 𝑥⃗ = 0 not
where 𝐵 = 𝐴 − 𝜆𝐼
Back then 𝑥⃗ = 0 Thus we want a solutions to 𝐴 − 𝜆𝐼 𝑥⃗ = 0 other than 𝑥⃗ = 0

Now we’re looking for an
eigenvector that cannot Recall:
be 0. Theorem : any invertible matrix − 𝐴 − 𝜆𝐼 − only has one solution.
Therefore, 𝐴 − 𝜆𝐼 needs to not be invertible.
and
Theorem : noninvertible matrices all have a determinant of 0.
Thus det 𝐴 − 𝜆𝐼 needs to equal 0.
Now we move forward by finding 𝜆 such that det 𝐴 − 𝜆𝐼 = 0

• Given a matrix, A, x is the eigenvector and l is
the corresponding eigenvalue if Ax = lx
• A must be square and the determinant of A - l I
must be equal to zero
Ax - lx = 0 iff (A - lI) x = 0
• Trivial solution is if x = 0
• The nontrivial solution occurs when det(A - lI) = 0
• Are eigenvectors unique?
• If x is an eigenvector, then bx is also an eigenvector
and l is an eigenvalue
A(bx) = b(Ax) = b(lx) = l(bx)
Problem
Solution
Problem
Solution
Section 2: Eigenvectors
In-class Quiz:
and Eigenvalues
Find 𝑥⃗ such that 𝐴𝑥⃗ = −1𝑥,
⃗ where
Problem
Solution
Find 𝑥⃗ such that 𝐴𝑥⃗ = −1𝑥,
⃗ where
Problem
Solution
2 4 0 1 2 0
rref
2 4 0 0 0 0
Thus 𝑥! = −2𝑥"
𝑥! −2𝑥" −2
𝑥⃗ = 𝑥 = = 𝑥" 𝑥" could be any nonzero scalar
" 𝑥" 1
Q&A

02 Tutorial Week3

Uploaded by

Copyright:

Available Formats

02 Tutorial Week3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

02 Tutorial Week3

Uploaded by

Copyright:

Available Formats

INFS7450 SOCIAL MEDIA ANALYTICS

Why we call those as spectral

Spectral Graph Theory:

Back then 𝑥⃗ = 0 Thus we want a solutions to 𝐴 − 𝜆𝐼 𝑥⃗ = 0 other than 𝑥⃗ = 0

Now we move forward by finding 𝜆 such that det 𝐴 − 𝜆𝐼 = 0

You might also like