Patterns often appear in a variety of large, real-world networks, and interesting physical phenomena are often explained by network topology as in the case of the bow-tie structure of the World Wide Web, or the small world phenomenon in social networks. The discovery and modelling of such regular patterns has a wide application from disease propagation to financial markets. In this work we describe a newly discovered regularly occurring striation pattern found in the PageRank ordering of adjacency matrices that encode real-world networks. We demonstrate that these striations are the result of well-known graph generation processes resulting in regularities that are manifest in the typical neighborhood distribution. The spectral view explored in this paper encodes a tremendous amount about the explicit and implicit topology of a given network, so we also discuss the interesting network properties, outliers and anomalies that a viewer can determine from a brief look at the re-ordered matrix.
The ordering of the Separator tree is based on an algorithm given by Blandford al @cite_27 . It removes vertices () from the graph in order to partition the structure into subgraphs of a fixed size. Separator trees were a result of trying to reduce the size of storage required for large graphs by isolating and thereby removing the need to store empty parts of the adjacency matrix.
@cite_27
1994840070
We consider the problem of representing graphs compactly while supporting queries efficiently. In particular we describe a data structure for representing n-vertex unlabeled graphs that satisfy an O(nc)-separator theorem, c < 1. The structure uses O(n) bits, and supports adjacency and degree queries in constant time, and neighbor listing in constant time per neighbor. This generalizes previous results for graphs with constant genus, such as planar graphs.We present experimental results using many "real world" graphs including 3-dimensional finite element meshes, link graphs of the web, internet router graphs, VLSI circuits, and street map graphs. Compared to adjacency lists, our approach reduces space usage by almost an order of magnitude, while supporting depthfirst traversal in about the same running time.