direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Journal and Magazine Articles

Discriminating graphs through spectral projections
Zitatschlüssel FHUKMKI-DGTSP-11
Autor Fay, Damien and Haddadi, Hamed and Uhlig, Steve and Kilmartin, Liam and Moore, Andrew W. and Kunegis, Jérôme and Iliofotou, Marios
Seiten 3458–3468
Jahr 2011
ISSN 0140-3664
DOI http://dx.doi.org/10.1016/j.comnet.2011.06.024
Journal Computer Networks
Jahrgang 55
Nummer 15
Verlag Elsevier
Zusammenfassung This paper proposes a novel non-parametric technique for clustering networks based on their structure. Many topological measures have been introduced in the literature to characterize topological properties of networks. These measures provide meaningful information about the structural properties of a network, but many networks share similar values of a given measure [1]. Furthermore, strong correlation between these measures occur on real-world graphs [2], so that using them to distinguish arbitrary graphs is difficult in practice [3]. Although a very complicated way to represent the information and the structural properties of a graph, the graph spectrum [4] is believed to be a signature of a graph [5]. A weighted form of the distribution of the graph spectrum, called the weighted spectral distribution (WSD), is proposed here as a feature vector. This feature vector may be related to actual structure in a graph and in addition may be used to form a metric between graphs; thus ideal for clustering purposes. To distinguish graphs, we propose to rely on two ways to project a weighted form of the eigenvalues of a graph into a low-dimensional space. The lower dimensional projection, turns out to nicely distinguish different classes of graphs, e.g. graphs from network topology generators , and , Internet application graphs [9], and dK-random graphs [10]. This technique can be used advantageously to separate graphs that would otherwise require complex sets of topological measures to be distinguished [9].
Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe