Graph cities: Their buildings, waves, and fragments

James Abello, Daniel Nakhimovich, Chengguizi Han, Mridul Aanjaneya

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


“Graph Cities” are 3D representations of maximal edge graph partitions. Each connected equivalence class corresponds to a “Building” that is formed by stacking graph “Edge Fragments”. The number of such graph edge fragments determines the height of the building. The overall number of buildings is the number of equivalence classes in the edge partition. A poly-log buck-etization of the size distribution of the equivalence classes is used to generate a 2D position for each bucket. For the buckets containing more than one equivalence class, we also generate a visual “Bush” representation. The Delaunay triangulation of these building locations determines the “street network” of the Graph City. The weight of a connection between two buildings on this street network is proportional to the intersection of the subgraph vertex sets represented by the two buildings. To handle equivalence classes (i.e., buildings) consisting of a large number of fragments, we use the notion of “Graph Waves” from [3]. Graph Waves are intervals of graph edge fragments with a “well-defined” beginning and end fragment. For computational purposes, the beginning and end fragments should satisfy a computationally “easy to verify” property. We illustrate Graph Cities obtained with the maximal edge partitions defined by the iterative edge core decomposition introduced in [4]. The graphs used include the Friendster social network (1.8 billion edges), a co-occurrence keywords network derived from the internet movie database (115 million edges), and a patents citation network (16.5 million edges). For graphs with up to 2 billion edges, all the elements of their corresponding Graph Cities are built in a few minutes (excluding I/O time) and storage proportional to the number of edges and vertices of a graph. Our ultimate goal is to obtain humanly-interpretable hierarchical descriptions of any graph that are accessible via a Unified Web Interface for Graph Analytics, without being constrained by the graph size.

Original languageEnglish (US)
JournalCEUR Workshop Proceedings
StatePublished - 2021
Event2021 Workshops of the EDBT/ICDT Joint Conference, EDBT/ICDT-WS 2021 - Nicosia, Cyprus
Duration: Mar 23 2021 → …

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


Dive into the research topics of 'Graph cities: Their buildings, waves, and fragments'. Together they form a unique fingerprint.

Cite this