Graph Cities and their Applications
Co-sponsored by the Berkeley Institute for Data Science and the School of Information
Graphs are a fundamental abstraction for modeling complex relational data across a wide range of domains, including social and citation networks, folklore studies, and multimedia datasets such as movie reviews and recipe ingredient–flavor networks. However, the visualization and analysis of massive graphs — whose scale exceeds memory capacity, human perceptual limits, and interactive rendering constraints — remain a significant challenge.
In this talk, we present Graph Cities1, a framework for human-interpretable, hierarchical exploration of large-scale networks. Graph Cities is based on an iterative fixed-point decomposition induced by degree peeling, which partitions any non-regular graph into layers of increasing structural density. Within each fixed point, the graph is further decomposed into waves and fragments using boundary-based structures that capture interactions between vertex sets. This multi-level organization enables scalable, interactive exploration of graphs containing up to several billion edges.
We demonstrate the effectiveness of Graph Cities on large real-world datasets, including the Friendster social network (1.8 billion edges), the Microsoft Academic citation network (1.6 billion edges), and the IMDb movie tag co-occurrence network (115 million edges). We further show how social media posts can be modeled as frequency-labeled graphs derived from directed ⟨entity, verb, entity⟩ triples, enabling their exploration within the Graph Cities framework. The resulting fixed-point decompositions and barycentric embeddings provide comprehensible yet fine-grained summaries of large collections of social media interactions2.
In addition, we introduce a complementary visualization based on stratified disk embeddings, derived from barycentric coordinates that encode vertex participation across fixed points3. Finally, we illustrate the flexibility of the approach through Graph Cities constructed from Frøken Jensens Kogebog, a late 19th-century Danish cookbook collection, offering a novel lens for exploring the structure of Danish cuisine at the beginning of the 20th century.
1 J. Abello, H. Zhang, D. Nakhimovich, C. Han and M. Aanjaneya, "Giga Graph Cities: Their Buckets, Buildings, Waves, and Fragments" in IEEE Computer Graphics and Applications, vol. 42, no. 03, pp. 53-64, May-June 2022, doi: 10.1109/MCG.2022.3172650.
2 J. Abello, T. R. Tangherlini, and H. Zhang, “A Max Flow Min Cut View of Social Media Posts,” in 13th International Conference on Data Science, Technology and Applications, DATA 2024, pp. 190–201.
3 J. Abello and H. Zhang, “Stratified Disk Views of Graph Edge Core Decompositions via Barycentric Coordinates,” in 14th International Conference on Complex Networks and their Applications, 2025.
Speakers
James Abello Monedero
Professor of Professional Practice
Department of Computer Science
Rutgers University
James Abuello is an experimental computer scientist focused on algorithms and systems for graph mining, relational learning, visualization, and sense making of massive data sets. James received his Ph.D. in combinatorial algorithms from the University of California, San Diego, and M.S. in operating systems from the University of California, Santa Barbara. He is the recipient of a University of California President’s Postdoctoral Fellowship in computer science and has been recognized with teaching awards at Rutgers and at the University of California, Santa Barbara.
James is the co-editor of External Memory Algorithms, Vol. 50 of the AMS-DIMACS series (with J. Vitter, 1999) , The Kluwer Handbook of Massive Data Sets (with P. Pardalos and M. Resende, 2002), and Discrete Methods in Epidemiology (with Graham Cormode, 2006). He is founding member of the newly created International Culture Analytics Network supported by the Danish Council on Independent Research.
Haoyang Zhang
Haoyang Zhang is a second-year Ph.D. student in the computer science department, Rutgers University, where he completed his master’s degree. He obtained his BS in communication engineering at University of Electronic Science and Technology of China in Chengdu.