Complex and Social Network Analysis (europython 2012)

Complex and Social Network Analysis in Python

View more presentations from rik0.

Social Network Analysis

This is a presentation I gave some days ago.
It is rather maths heavy and the point of view is more maths than computer science.

Social Network Analysis

View more presentations from rik0.

Networks: an introduction

I usually do not discuss here things closely related to my research area. This is for a number of reasons: for example, I usually write this blog in my spare time and I focus on different subjects. There are exceptions... for example I'm writing about PageRank (here, here and I have not yet finished), which is rather close to a specific part of what I'm doing (no, I'm not re-writing Google from scratch ;) ).

Nowadays I have lots of interest in network and graph theory. I like it because it keeps my maths fresh (I miss maths a lot, in fact) and most computer science and engineering subjects can be better grasped with a sound and complete (pun intended) understanding of graph theory.



I recently found a wonderful book, which is "Networks: An Introduction" by M.E.J. Newman. This is not about "computer networks" (though they are dealt with). It is about the maths behind networks. It is a single book which cover all the basis of network theory.

Different kinds of networks are described (biological, social, information). Network properties, metrics and measures are defined, and results on average properties for each kind of network are given, together with the large-scale description of such networks. Then, a whole lot of computer algorithms are presented. Models to generate networks (random graphs, Barabasi and Albert model, Strogatz and Watts model) are explained and eventually network processes (epidemics, percolation, node removal/addition, dynamic systems, search) are presented. Basically, it's all there.

Moreover, the book is very readable, even with little experience on the subject and each part is mostly independent. That is to say, it is possible to start reading almost from any point, which makes the book a great reference. But it is also a great introduction to the subject. And > 300 references mean that the book is a great hub to start further explorations of the world of networks.

Networks, Social Networks, Complex Networks

Introducing Page Rank Maths

In my previous post, I started introducing Google PageRank. Now I'm starting to dig into PageRank maths. PageRank definition is not very "computation oriented".

r(Pi) = ∑ Pj ∈ Li  r(Pj) |Pj|

(2)

There is not a clear temporal ordering of pages or any other sensible starting point. Hopefully, an iterative method may converge to the result. So we subscript the rank with a number indicating the step and express the (i)-th step in terms of the (i−1)-step:

rk(Pi) = ∑ Pj ∈ Li  rk−1(Pj) |Pj|

(3)

Of course, we are not happy with the whole "may-converge" thing and would rather have some precise results. The first step is using some convenient notation: formula 2.2 is easy to grasp but awkward to manipulate.

The idea here is express the equations in matrix form. Let L = (e_ij) be the adjacency matrix of our graph. In other words:

eij = 1    if there is a link from i to j 0    otherwise

(4)

Then we consider the matrix H = ―D⁻¹·A, where ―D = max(I, D) and D is the diagonal matrix of the degrees of the nodes. In Python we can compute H with:

import numpy as np

def h_matrix(adjacency_matrix):
    degrees = np.sum(adjacency_matrix, axis=1)
    degrees[degrees==0] = 1
    return np.dot(np.diag(1./degrees), adjacency_matrix)


# ...

The H j-th row can be interpreted as the distribution of probability for jumping from node j to each other node. If our graph is the web, H has billions of rows (and columns) but in average each page has about 10 out links. H is a very sparse matrix, indeed.

Let π be the rank-vector. Then we can reformulate the problem as:

πT = πT·H

(5)

Basically we are looking for the eigenvector associated with the eigenvalue λ₁ = 1. The idea here is to use the power method. The power method is an iterative method that computes the eigenpair (λ₁, π) of a matrix A. A must satisfy some basic hypotheses for the power method to work. Let {λ₁,…,λ_n} be the set of eigenvalues of A, then it must be true that |λ₁| > |λ₂| ≥ … ≥ |λ_m|. As a consequence, λ₁ ∈ \mathbbR.

Then it is possible to compute (λ₁, π) with:

yn=Axn xn + 1 = yn cn

(6)

Then x_n→ x and c_n→λ₁.

Here c_n is a scaling factor; e.g. λ₁, ||Aⁿx₀||, the component of y_n of maximal magnitude. Now, the fact that we suggested λ₁ as a possible scaling factor is not a mistake: it is proved that the actual Google matrix has λ₁.

Moreover x₀ ∉ R(A−λ₁I), where R(M)={v|v=Ax}. However, in practice "most" starting vectors x₀ are good.

If H were a usable Google Matrix, things would be very nice. H is essentially the matrix of a random walk over the graph. We could just see the whole thing as a Markov process. More on this can be found in [3].

The analogy with Markov processes here can give us some insight on the problems with the H matrix. If we interpret nodes as states, we can see that a closed class of state (possibly a singleton) would be a serious issue. And any node with no outgoing links constitutes such a class.

In the Markov chain interpretation, if such a node is reachable, then we would just remain there. Such nodes would be rank sinks. In such a setting, every web site with no outgoing links would acquire a rank far superior to its actual importance. Using Markov chains terminology, the H matrix is substochastic.

Another problem is related to cycles. E.g., consider the matrix

C = 0 1 1 0

Then: C²ⁿ = I and C²ⁿ⁺¹ = C. As a consequence we cannot expect to converge (notice, here we have eigenvalues with same magnitude, so we know that the power method is not going to work).

Luckily enough, these problems are rather easy to fix modifying the matrix. More on this, later!

References

[1]

M. Franceschet. PageRank: Standing on the shoulders of giants. arxiv.org.

[2]

M.E.J. Newman. The structure and function of complex networks. Arxiv preprint cond-mat/0303516, 2003.

[3]

M.E.J. Newman. Networks: An Introduction. Oxford University Press, 2010.

[4]

L Page and S Brin. The pagerank citation ranking: Bringing order to the web. 1998.

PageRank, SEO, Python, Computing, Algorithm

Other applications of the ideas behind Page Rank

One of the problem a search engine has to solve is to sort the potentially very long list of matches for a given query with a sensible ordering. Sensible here means that ideally the more interesting results come first.

Many strategies could be applied here (and there is a lot of ongoing research on the subject). Many complex strategies are already applied. However, the basic idea [4] Google used was very simple (as an idea) and very robust.

It is easy to see that the idea was simple. Let r(P_i) be the ranking of page P_i, L_i be the set of pages linking to P_i, and |P_i| be the number of outbound links of |P_i| then:

r(Pi) = ∑ Pj ∈ Li  r(Pj) |Pj|

(1)

Simple, indeed. With the minor problem that we have no starting point to trigger the computation. Luckily enough, iterative methods come to help. More on this in a few paragraph. I have not yet clarified the "robust" part.

In fact the kinds of ideas underlying the PageRank are rather old. Similar ideas have been spotted in bibliometrics, econometrics and sociometrics. This is not to be considered a defect (lack of novelty), rather I consider it a feature as in "already field-tested".

Using words, PageRank states that a page is important if many important pages link to it. Which is not different from the usual definition of importance of journals, where a journal is important if many important journals contain articles referring to articles in that journal. Well, in the journal world things are easier as there are far less journals than web pages and there is a clear temporal order that can be used. Moreover, articles usually cite only papers written before them (at least until some research has a paper describing his implementation of time-machines, then he could easily refer to articles not yet published).

In 1949 Seeley proposed to "measure" the popularity of a child (he was researching relationships in children social group) considering the popularity of the children which enlisted him among his friends. That is, once again, something like P_i = f(F₁¹,...,F₁^k), where F₁^j is a child who listed 1 among his friends. The very same criterion can be applied to recommendations.

Leontief won Nobel Prize for Economy for his ideas on econometrics on the input-output model, which is yet an application of the same underlying ideas. Here I won't give further details. These example come from [1] where further details are given.

I explore further how to compute the PageRank here.