Name
Abstract | ||
|---|---|---|
We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph's spectrum, leaving the eigenvectors unchanged. We validate this hypothesis for several large social, collaboration, authorship, rating, citation, communication and tagging networks, covering unipartite, bipartite, signed and unsigned graphs. Following these observations, we introduce a link prediction algorithm based on the extrapolation of a network's spectral evolution. This new link prediction method generalizes several common graph kernels that can be expressed as spectral transformations. In contrast to these graph kernels, the spectral extrapolation algorithm does not make assumptions about specific growth patterns beyond the spectral evolution model. We thus show that it performs particularly well for networks with irregular, but spectral, growth patterns. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1871437.1871533 | CIKM |
Keywords | Field | DocType |
growth pattern,graph kernel,network growth,spectral transformation,spectral evolution,specific growth pattern,spectral evolution model,common graph kernel,spectral extrapolation algorithm,unsigned graph,large network,eigenvectors,spectrum,eigenvalue decomposition,spectral graph theory | Adjacency matrix,Data mining,Graph,Mathematical optimization,Spectral graph theory,Graph energy,Computer science,Bipartite graph,Algorithm,Extrapolation,Eigendecomposition of a matrix,Eigenvalues and eigenvectors | Conference |
Citations | PageRank | References |
19 | 1.11 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jérôme Kunegis | 1 | 874 | 51.20 |
| Damien Fay | 2 | 135 | 14.41 |
| Christian Bauckhage | 3 | 1979 | 195.86 |