Simultaneous Matrix Orderings for Graph Collections.

Area of Science:

• Graph theory and network visualization
• Computational topology and data analysis
• Spatial statistics and autocorrelation

Background:

• Undirected graphs model interacting systems like social networks and brain activity.
• Graph structure is visualized via adjacency matrices, where row/column ordering is crucial.
• Visualizing collections of graphs requires a single ordering for multiple matrices.

Purpose of the Study:

• To develop a collection-aware approach for simultaneous graph matrix ordering.
• To address information loss in current union-based methods for graph collections.
• To introduce Moran's I as a superior quality metric for matrix ordering.

Main Methods:

• Proposed a collection-aware strategy applied to leaf order and barycenter heuristics.
• Utilized Moran's I, a spatial autocorrelation metric, for evaluating ordering quality.
• Leveraged Traveling Salesperson Problem (TSP) algorithms for computing optimal orderings.

Main Results:

• Collection-aware approach matched or improved performance over union methods.
• Moran's I effectively captures a wider range of patterns than standard metrics.
• Moran's I-based collection-aware leaf order demonstrated superior performance on real-world data.

Conclusions:

• The collection-aware method preserves critical information in graph collections.
• Moran's I is a robust metric for assessing graph matrix ordering quality.
• The proposed methods offer significant improvements without substantial computational overhead.