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 1641749581 2022989269 2166220529
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. This paper proposes a novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set. A graph transaction is represented by an adjacency matrix, and the frequent patterns appearing in the matrices are mined through the extended algorithm of the basket analysis. Its performance has been evaluated for the artificial simulation data and the carcinogenesis data of Oxford University and NTP. Its high efficiency has been confirmed for the size of a real-world problem. This paper describes a new algorithm for document binarization, building upon recent work in energy-based segmentation methods. It uses the Laplacian operator to assess the local likelihood of foreground and background labels, Canny edge detection to identify likely discontinuities, and a graph cut implementation to efficiently find the minimum energy solution of an objective function combining these concepts. The results of this algorithm place it near the top on both the DIBCO-09 and H-DIBCO assessments. In this study, we examine the use of graph ordering algorithms for visual analysis of data sets using visual similarity matrices. Visual similarity matrices display the relationships between data items in a dot-matrix plot format, with the axes labeled with the data items and points drawn if there is a relationship between two data items. The biggest challenge for displaying data using this representation is finding an ordering of the data items that reveals the internal structure of the data set. Poor orderings are indistinguishable from noise whereas a good ordering can reveal complex and subtle features of the data. We consider three general classes of algorithms for generating orderings: simple graph theoretic algorithms, symbolic sparse matrix reordering algorithms, and spectral decomposition algorithms. We apply each algorithm to synthetic and real world data sets and evaluate each algorithm for interpretability (i.e., does the algorithm lead to images with usable visual features?) and stability (i.e., does the algorithm consistently produce similar results?). We also provide a detailed discussion of the results for each algorithm across the different graph types and include a discussion of some strategies for using ordering algorithms for data analysis based on these results.