Graph Cities are 3D visual representations of partitions of a graph edge set into maximal connected subgraphs each of which is called a fixed point of degree peeling. Each such connected subgraph is visually represented as a Building. A poly-log bucketization of the size distribution of the subgraphs represented by the buildings generates a 2D position for each bucket. The Delaunay triangulation of the bucket building locations determines the street network. We illustrate Graph Cities for the Friendster social network(1.8 billion edges), a co-occurrence keywords network derived from the Internet Movie Database (115 million edges), and a patent citation network(16.5 million edges). Up to 2 billion edges, all the elements of their corresponding Graph Cities are rendered in few minutes (excluding I/O time). The actual Graph Cities computation takes about 2 hours on a 64 GB RAM commodity computer. Our ultimate goal is to provide tools to build humanly interpretable descriptions of any graph, without being constrained by the graph size. It consists of four sub-modules: wave-decomposition, Graph_City_Web, fpViewer and graph-strata.

Web interactions are fully tested using Chrome. There are some issues with Safari. Therefore, we recommand for the current version to only use Chrome as a browser. A video illustrating our current interface can be accessed at here.

The main 2022 publication is:

@article{Abello2022GigaGC,
  title={Giga Graph Cities: Their Buckets, Buildings, Waves, and Fragments},
  author={James Abello and H. Zhang and Daniel Nakhimovich and Chengguizi Han and Mridul Aanjaneya},
  journal={IEEE Computer Graphics and Applications},
  year={2022},
  volume={42},
  pages={53-64}
}

Funding

This is an NSF-funded project (NSF IIS-1563816 and IIS-1563971), led by Prof. James Abello. It is partially funded by Nokia Bell Labs, Siemens Research, and mgvis.com. It constitutes a major part of the incoming Ph.D. thesis of Haoyang Zhang.

Credits

Preprocessed Data Sets

Large

Name Source V E cc FP
com-friendster SNAP 65608366 1806067135 1 72
ogbn-papers100M OGB 111059956 1614062356 151 159
movies-tag-cooccurence IMDb 218052 115050370 38 78

Medium

name Source V E cc FP
ogbn-products OGB 2400608 61859012 4237 102
ogbn-proteins OGB 132534 39561252 1 157
ogbn-mag OGB 1134649 21090258 1 64
cit-Patents SNAP 3774768 16518947 3627 41

Small

name Source V E cc FP
Pandora papers ICIJ Offshore Leaks Database 1968951 2832596 31347 31
ogbn-arxiv OGB 169343 1157799 1 22

Tiny

name V E cc FP
Danish Fabula 19738 28292 414 6
Game of Thrones 796 2823 1 9
Starwars 111 444 1 7

Sample Findings

A collection of “interesting” patterns can be accessed at Graph City Patten Gallery.

Papers

If you use our code, please consider citing our paper.

@article{Abello2022GigaGC,
  title={Giga Graph Cities: Their Buckets, Buildings, Waves, and Fragments},
  author={James Abello and H. Zhang and Daniel Nakhimovich and Chengguizi Han and Mridul Aanjaneya},
  journal={IEEE Computer Graphics and Applications},
  year={2022},
  volume={42},
  pages={53-64}
}

@inproceedings{Abello2021GraphCT,
  title={Graph Cities: Their Buildings, Waves, and Fragments},
  author={James Abello and Daniel Nakhimovich and Chengguizi Han and Mridul Aanjaneya},
  booktitle={EDBT/ICDT Workshops},
  year={2021}
}

@article{Abello2020GraphW,
  title={Graph Waves},
  author={James Abello and Daniel Nakhimovich},
  journal={Big Data Res.},
  year={2020},
  volume={29},
  pages={100327}
}

@article{Abello2013FixedPO,
  title={Fixed points of graph peeling},
  author={James Abello and François Queyroi},
  journal={2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013)},
  year={2013},
  pages={256-263}
}

Flowchart of Graph Cities Infrastructure