Stress Centrality in Heterogeneous Multilayer Networks: Heuristics-Based Detection

Centrality metrics for simple graphs are well-defined. For each centrality measure, multiple main-memory algorithms exist for their computation. With main memory algorithms, the size of the graph that can be analyzed is bounded by the available memory. For the analysis of complex data, it has been shown that multilayer networks (or MLNs) are better suited as it has a number of advantages for modeling and provides semantic clarity. Briefly, MLNs are layers where each layer is a simple graph and further nodes from two different layers may also be connected. MLNs with different node sets and interlayer edges are termed heterogeneous MLNs (or HeMLNs) and are the focus of this paper. Hence, there is a need for algorithms to compute centrality metrics directly on the MLN representation.Currently, centrality metrics are not defined for Heterogeneous Multilayer Networks (HeMLNs), which are widely used for modeling complex data sets. Typically, HeMLNs are converted into a simple graph using aggregation and projection alternatives for computing centrality metrics using the traditional main-memory algorithms. However, this approach has been shown to lose information and structure (and hence semantics) and makes interpreting the results difficult.In this paper, we present a definition of stress (betweenness) centrality for HeMLNs and propose a heuristic-based algorithm to improve the accuracy of computed metrics with respect to ground truth. We provide intuition behind the heuristic proposed and provide extensive experimental results on different types of graphs with diverse characteristics to support our heuristics. Large synthetic data sets are used to control graph characteristics to validate the hypothesis and accuracy consistency. For computation, we use the decoupling approach, proposed specifically for MLNs, which has been shown to be significantly more efficient than the computation of ground truth. We validate that as well with our algorithm.