Graph Cities and Their Applications (James Abello Monedero & Haoyang Zhang)

Why It Matters

This framework lets researchers visualize and dissect ultra‑large networks without predefined semantics, accelerating insights across tech, media, and humanities.

Key Takeaways

• Graph Cities visualize billions of connections as city‑like structures.
• Minimum‑degree removal reveals hierarchical “waves” forming building layers.
• Any network can be decomposed into fixed‑point fragments.
• Waves map narratives, social media, movies without prior semantic knowledge.
• Matrix and barycentric coordinates unify multi‑role entities across networks.

Summary

The talk titled “Graph Cities and their Applications” introduced a method for turning massive graphs—up to billions of edges—into city‑like visualizations that can be explored interactively.

The core technique iteratively removes nodes of minimum degree, generating a sequence of “waves” or fixed‑point fragments. Each wave becomes a floor of a virtual building, and stacking these floors yields the cityscape. The process runs on a laptop in minutes, with rendering in seconds.

Examples included a historic phone‑call graph from Bell Labs, a movie‑similarity network where “Chinese Odyssey” emerged as a cluster, and a multi‑role individual (Tim) whose connections were split across several fixed points, illustrated with barycentric coordinates.

By decomposing any network into manageable fragments, analysts can apply domain‑specific tools to each piece and recombine results, opening new avenues for social‑media monitoring, narrative analysis, and cross‑domain network studies.

Original Description

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.

Co-sponsored by the Berkeley Institute for Data Science, the School of Information, and the Department of Scandinavian.

Speakers

James Abello Monedero

Professor of Professional Practice

Department of Computer Science

Rutgers University

James Abello Monedero 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 fourth-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.

More info:

https://www.ischool.berkeley.edu/events/2026/graph-cities-and-their-applications