Centrality measures for simple graphs are well-defined and several main-memory algorithms exist. Simple graphs are not adequate for modeling complex data sets with multiple types of - entities and relationships. Multilayer networks (MLNs) have been shown to be better suited, but there are very few algorithms for centrality metric computation directly on MLNs. Typically, MLN layers are converted (aggregated or projected) to simple graphs using Boolean AND or OR operators to compute centrality, which is not only inefficient, but incurs loss of structure and semantics. We start with a formal definition of closeness centrality for homogeneous MLNs (or HoMLNs) that is compatible with the simple graph definition. As we use the decoupling-based approach directly on MLNs without aggregating HoMLN layers in any way, we provide some observations to understand the challenges. We also formally prove a couple of important limits on the information that is needed from the layer closeness computation for the composition approach. We propose two heuristic-based algorithms to compute closeness centrality on a HoMLN directly using the decoupling-based approach. Individual results from layers (or simple graphs) of a MLN are used and a composition function is applied to compute the closeness centrality for the HoMLN. The challenge is the efficient computation and accuracy preservation with respect to ground truth. Since these algorithms do not have complete information of the HoMLN, computing a global measure such as closeness centrality is a challenge. Hence, these algorithms rely on heuristics derived from intuition. Advantages to this approach are that it lends itself to parallelism and is more efficient as compared to the aggregated approach used as ground truth in this paper. Two heuristics have been presented for composition and their accuracy and efficiency have been validated on a large number of synthetic, real-world like, and real-world graphs with diverse characteristics.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Closeness Centrality: Definition, and Its Computation for Homogeneous Multilayer Networks

  • Hamza Pavel,
  • Anamitra Roy,
  • Abhishek Santra,
  • Sharma Chakravarthy

摘要

Centrality measures for simple graphs are well-defined and several main-memory algorithms exist. Simple graphs are not adequate for modeling complex data sets with multiple types of - entities and relationships. Multilayer networks (MLNs) have been shown to be better suited, but there are very few algorithms for centrality metric computation directly on MLNs. Typically, MLN layers are converted (aggregated or projected) to simple graphs using Boolean AND or OR operators to compute centrality, which is not only inefficient, but incurs loss of structure and semantics. We start with a formal definition of closeness centrality for homogeneous MLNs (or HoMLNs) that is compatible with the simple graph definition. As we use the decoupling-based approach directly on MLNs without aggregating HoMLN layers in any way, we provide some observations to understand the challenges. We also formally prove a couple of important limits on the information that is needed from the layer closeness computation for the composition approach. We propose two heuristic-based algorithms to compute closeness centrality on a HoMLN directly using the decoupling-based approach. Individual results from layers (or simple graphs) of a MLN are used and a composition function is applied to compute the closeness centrality for the HoMLN. The challenge is the efficient computation and accuracy preservation with respect to ground truth. Since these algorithms do not have complete information of the HoMLN, computing a global measure such as closeness centrality is a challenge. Hence, these algorithms rely on heuristics derived from intuition. Advantages to this approach are that it lends itself to parallelism and is more efficient as compared to the aggregated approach used as ground truth in this paper. Two heuristics have been presented for composition and their accuracy and efficiency have been validated on a large number of synthetic, real-world like, and real-world graphs with diverse characteristics.