Archive for the ‘Spectral Evolution Model’ Category

Jérôme Kunegis

Sunday, November 20th, 2011

Jérôme Kunegis

When I read things like René Pickhardt saying: “One of the first things I did @ my Institute when starting my PhD program was reading the PhD thesis of Jérôme Kunegis.” with no reference or link, it just drives me crazy! A little bibliographic instinct is a good thing but I think the breeding when a bit far in my case. 😉

Anyway, your gain. This is the homepage for Jérôme Kunegis where you will find:

PhD Thesis

I wrote my PhD thesis On the Spectral Evolution of Large Networks under supervision of Prof. Dr. Steffen Staab, Prof. Dr. Klaus Obermayer and Prof. Dr. Christian Bauckhage in 2011.

Download: “On the Spectral Evolution of Large Networks” (print version)

In my PhD thesis, I studied the spectral characteristics of large dynamic networks and formulate the spectral evolution model. The spectral evolution model applies to networks that evolve over time, and describes their spectral decompositions such as the eigenvalue and singular value decomposition. My main result is an interpretation of the spectrum and eigenvectors of networks in terms of global and local effects. I show empirically that the spectrum describes a network on the global level, whereas eigenvectors describe a network at the local level, and derive from this several new link prediction methods.

From page 2 of the thesis:

In this thesis, spectral graph theory is used to predict which nodes of a network will be connected in the future. This problem is called the link prediction problem, and is known under many diff erent names depending on the network to which it is applied. For instance, fi nding new friends in a social network, recommending movies and predicting which scientists will publish a paper together in the future are all instances of the link prediction problem. Several link prediction algorithms based on spectral graph theory are already known in the literature. However there is no general theory that predicts which spectral link prediction algorithms work best, and under what circumstances certain spectral link prediction algorithms work better than others. To solve these problems, this thesis proposes the spectral evolution model : A model that describes in detail how networks change over time in terms of their eigenvectors and eigenvalues. By observing certain growth patterns in actual networks, we are able to predict the growth of networks accurately, and thus can implement relevant recommender systems for all types of network datasets.

Jérôme steps over, “This problem is called the link prediction problem, and is known under many diff erent names depending on the network to which it is applied.”, the subject identity problem to solve a problem that may be useful with subject identity.

What if instead of thinking of “line prediction” as in a recommender system but in terms of “this representative” represents the same subject as “that representative?”

You will also find all of his publications with download links.

Be mindful that this work underlies the approach in Graphity which is retrieving 10,000 nodes per second from social networks.