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 idea of finding order in visual representations of matrices, especially adjacency matrices of graphs, has a long history. McCormick al introduced the Bond Energy Algorithm @cite_9 , which provided a method of reordering the columns and rows of matrices so that larger values were grouped together. This method used a nearest neighbor heuristic to overcome the @math possible permutations, and is among the earliest algorithms that may be used as a graph clustering algorithm.
@cite_9
2119430004
A new cluster-analysis method, the bond energy algorithm, has been developed recently; it operates upon a raw input object-object or object-attribute data array by permuting its rows and columns in order to find informative variable groups and their interrelations. This paper describes the algorithm and illustrates by several examples its use for both problem decomposition and data reorganization.