How to choose the most appropriate centrality measure? A decision tree approach

• URL: http://arxiv.org/abs/2003.01052v7
• Date: Wed, 19 Jun 2024 15:03:45 GMT
• Title: How to choose the most appropriate centrality measure? A decision tree approach
• Authors: Pavel Chebotarev, Dmitry Gubanov,
• Abstract summary: We introduce the culling method, which relies on the expert concept of centrality behavior on simple graphs. We apply this approach to a diverse set of 40 centralities, including novel kernel-based indices. Applying the culling method provides insightful findings on some centrality indices.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Centrality metrics play a crucial role in network analysis, while the choice of specific measures significantly influences the accuracy of conclusions as each measure represents a unique concept of node importance. Among over 400 proposed indices, selecting the most suitable ones for specific applications remains a challenge. Existing approaches -- model-based, data-driven, and axiomatic -- have limitations, requiring association with models, training datasets, or restrictive axioms for each specific application. To address this, we introduce the culling method, which relies on the expert concept of centrality behavior on simple graphs. The culling method involves forming a set of candidate measures, generating a list of as small graphs as possible needed to distinguish the measures from each other, constructing a decision-tree survey, and identifying the measure consistent with the expert's concept. We apply this approach to a diverse set of 40 centralities, including novel kernel-based indices, and combine it with the axiomatic approach. Remarkably, only 13 small 1-trees are sufficient to separate all 40 measures, even for pairs of closely related ones. By adopting simple ordinal axioms like Self-consistency or Bridge axiom, the set of measures can be drastically reduced making the culling survey short. Applying the culling method provides insightful findings on some centrality indices, such as PageRank, Bridging, and dissimilarity-based Eigencentrality measures, among others. The proposed approach offers a cost-effective solution in terms of labor and time, complementing existing methods for measure selection, and providing deeper insights into the underlying mechanisms of centrality measures.

Related papers

• A multi-criteria approach for selecting an explanation from the set of counterfactuals produced by an ensemble of explainers [4.239829789304117]
  We propose to use a multi-stage ensemble approach that will select single counterfactual based on the multiple-criteria analysis. The proposed approach generates fully actionable counterfactuals with attractive compromise values of the considered quality measures.
  arXiv  Detail & Related papers  (2024-03-20T19:25:11Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Cutting Plane Selection with Analytic Centers and Multiregression [2.8757106397019228]
  We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space.
  arXiv  Detail & Related papers  (2022-12-14T14:06:27Z)
• Composed Image Retrieval with Text Feedback via Multi-grained Uncertainty Regularization [73.04187954213471]
  We introduce a unified learning approach to simultaneously modeling the coarse- and fine-grained retrieval. The proposed method has achieved +4.03%, +3.38%, and +2.40% Recall@50 accuracy over a strong baseline.
  arXiv  Detail & Related papers  (2022-11-14T14:25:40Z)
• Measurement-based Admission Control in Sliced Networks: A Best Arm Identification Approach [68.8204255655161]
  In sliced networks, the shared tenancy of slices requires adaptive admission control of data flows. We devise a joint measurement and decision strategy that returns a correct decision with a certain level of confidence.
  arXiv  Detail & Related papers  (2022-04-14T12:12:34Z)
• Risk Consistent Multi-Class Learning from Label Proportions [64.0125322353281]
  This study addresses a multiclass learning from label proportions (MCLLP) setting in which training instances are provided in bags. Most existing MCLLP methods impose bag-wise constraints on the prediction of instances or assign them pseudo-labels. A risk-consistent method is proposed for instance classification using the empirical risk minimization framework.
  arXiv  Detail & Related papers  (2022-03-24T03:49:04Z)
• A Typology for Exploring the Mitigation of Shortcut Behavior [29.38025128165229]
  We provide a unification of various XIL methods into a single typology by establishing a common set of basic modules. In our evaluations, all methods prove to revise a model successfully. However, we found remarkable differences in individual benchmark tasks, revealing valuable application-relevant aspects.
  arXiv  Detail & Related papers  (2022-03-04T14:16:50Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  We propose a novel end-to-end learning-based framework to generate dense point clouds. We first formulate the problem explicitly, which boils down to determining the weights and high-order approximation errors. Then, we design a lightweight neural network to adaptively learn unified and sorted weights as well as the high-order refinements.
  arXiv  Detail & Related papers  (2020-11-25T14:00:18Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  We first review automatic relevance determination (ARD) and analytically demonstrate the need to additional regularization or thresholding to achieve sparse models. We then discuss two classes of methods, regularization based and thresholding based, which build on ARD to learn parsimonious solutions to linear problems.
  arXiv  Detail & Related papers  (2020-05-18T14:08:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.