Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pržulj, N., Corneil, D.G., Jurisica, I.: Modeling interactome: scale-free or geometric? Bioinformatics 20(18), 3508–3515
Batagelj, V.: Zaveršnik, M.: Generalized Cores. ArXiv Computer Science e-prints (2002)
Seidman, S.B.: Network structure and minimum degree. Social Networks, 269–287 (1983)
Wasserman, S., Faust, K.: Social network analysis: Methods and applications. Cambridge University Press, Cambridge (1994)
Alvarez-Hamelin, I., Dall’Asta, L., Barrat, A., Vespignani, A.: DELIS-TR-0166 - k-core decomposition: A tool for the visualization of large scale networks. techreport 0166, DELIS – Dynamically Evolving Large-scale Information Systems (2004)
Alvarez-Hamelin, I., Barrat, A., Dall’Asta, L., Vespignani, A.: k-core decomposition: A tool for the analysis of large scale internet graphs. Computer Science, cs.NI/0511007 (2005)
Batagelj, V., Mrvar, A.: Pajek - Analysis and Visualization of Large Networks, vol. 2265 (January 2002)
Wuchty, S., Almaas, E.: Peeling the yeast protein network. Proteomics (2005)
Bader, G.D., Hogue, C.W.: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, 2 (2003)
Gaertler, M., Patrignani, M.: DELIS-TR-0003 - dynamic analysis of the autonomous system graph. In: Proceedings 0003, 2004, IPS 2004 (Inter-Domain Performance and Simulation) (2004)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, Heidelberg (2001)
Bonato, A.: A survey of models of the web graph. In: Proceedings of the Workshop on Combinatorial and Algorithmic Aspects of Networking (CANN 2004), Springer, Heidelberg (2004)
Chung, F., Lu, L., Dewey, T.G., Galas, D.J.: Duplication models for biological networks. Journal of Computational Biology 10(5), 677–687 (2003)
TREC: The.gov test collection (last accessed August 28, 2006)
Hall, B.H., Jaffe, A.B., Trajtenberg, M.: The nber patent citation data file: Lessons, insights and methodological tools. NBER Working Papers 8498, National Bureau of Economic Research, Inc (October 2001) (last accessed August, 30 2006), http://ideas.repec.org/p/nbr/nberwo/8498.html
Wan, X., Janssen, J., Kalyaniwalla, N., Milios, E.: Statistical analysis of dynamic graphs. In: Proceedings of AISB 2006: Adaptation in Artificial and Biological Systems, vol. 3, pp. 176–179 (2006)
Angelova, R., Weikum, G.: Graph-based text classification: Learn from your neighbors. In: 29th Annual International ACM SIGIR Conference on Research & Development on Information Retrieval (SIGIR 2006), Association for Computing Machinery (ACM), pp. 485–492. ACM, New York (2006)
Erdős, P., Rényi, A.: On random graphs. Publicationes Mathematicae (1959)
Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci (1961)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Structures Algorithms (2001)
Chung, F., Lu, L.: Coupling online and offline analyses for random power law graphs. In: Internet Mathematics (2003)
Siek, J.G., Lee, L.Q., Lumsdaine, A.: The boost graph library: User guide and reference manual. Addison-Wesley Longman Publishing Co., Inc., Boston (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Healy, J., Janssen, J., Milios, E., Aiello, W. (2008). Characterization of Graphs Using Degree Cores. In: Aiello, W., Broder, A., Janssen, J., Milios, E. (eds) Algorithms and Models for the Web-Graph. WAW 2006. Lecture Notes in Computer Science, vol 4936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78808-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-78808-9_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78807-2
Online ISBN: 978-3-540-78808-9
eBook Packages: Computer ScienceComputer Science (R0)