Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Characterization of Graphs Using Degree Cores
verfasst von : John Healy, Jeannette Janssen, Evangelos Milios, William Aiello
Erschienen in: Algorithms and Models for the Web-Graph
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Generative models are often used in modeling real world graphs such as the Web graph in order to better understand the processes through which these graphs are formed. In order to determine if a graph might have been generated by a given model one must compare the features of that graph with those generated by the model. We introduce the concept of a hierarchical degree core tree as a novel way of summarizing the structure of massive graphs. The degree core of level
k
is the unique subgraph of minimal degree
k
. Hierarchical degree core trees are representations of the subgraph relationships between the components of the degree core of the graph, ranging over all possible values of
k
. We extract features related to the graph’s local structure from these hierarchical trees. Using these features, we compare four real world graphs (a web graph, a patent citation graph, a co-authorship graph and an email graph) against a number of generative models.