A multi-core periphery perspective: Ranking via relative centrality

• URL: http://arxiv.org/abs/2406.04487v1
• Date: Thu, 6 Jun 2024 20:21:27 GMT
• Title: A multi-core periphery perspective: Ranking via relative centrality
• Authors: Chandra Sekhar Mukherjee, Jiapeng Zhang,
• Abstract summary: Community and core-periphery are two widely studied graph structures. The impact of inferring the core-periphery structure of a graph on understanding its community structure is not well utilized. We introduce a novel for graphs with ground truth communities, where each community has a densely connected part (the core) and the rest is more sparse (the periphery)
• Score: 4.33459568143131
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community and core-periphery are two widely studied graph structures, with their coexistence observed in real-world graphs (Rombach, Porter, Fowler \& Mucha [SIAM J. App. Math. 2014, SIAM Review 2017]). However, the nature of this coexistence is not well understood and has been pointed out as an open problem (Yanchenko \& Sengupta [Statistics Surveys, 2023]). Especially, the impact of inferring the core-periphery structure of a graph on understanding its community structure is not well utilized. In this direction, we introduce a novel quantification for graphs with ground truth communities, where each community has a densely connected part (the core), and the rest is more sparse (the periphery), with inter-community edges more frequent between the peripheries. Built on this structure, we propose a new algorithmic concept that we call relative centrality to detect the cores. We observe that core-detection algorithms based on popular centrality measures such as PageRank and degree centrality can show some bias in their outcome by selecting very few vertices from some cores. We show that relative centrality solves this bias issue and provide theoretical and simulation support, as well as experiments on real-world graphs. Core detection is known to have important applications with respect to core-periphery structures. In our model, we show a new application: relative-centrality-based algorithms can select a subset of the vertices such that it contains sufficient vertices from all communities, and points in this subset are better separable into their respective communities. We apply the methods to 11 biological datasets, with our methods resulting in a more balanced selection of vertices from all communities such that clustering algorithms have better performance on this set.

Related papers

• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Curvature-based Clustering on Graphs [14.136746708037402]
  We study algorithms, which exploit the geometry of the graph to identify densely connected substructures, which form clusters or communities. Our method implements discrete Ricci curvatures and their associated geometric flows, under which the edge weights of the graph evolve to reveal its community structure.
  arXiv  Detail & Related papers  (2023-07-19T17:35:08Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering [4.264842058017711]
  Community detection is a critical challenge in analysing real graphs. This article proposes three new, general, hierarchical frameworks to deal with this task. We compare over a hundred module combinations on the Block Model graphs and real-life datasets.
  arXiv  Detail & Related papers  (2023-03-21T22:12:53Z)
• A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource [87.7460720701592]
  This paper introduces formulaic definition, evaluation, and development in this field. The taxonomy of deep graph clustering methods is presented based on four different criteria, including graph type, network architecture, learning paradigm, and clustering method. The applications of deep graph clustering methods in six domains, including computer vision, natural language processing, recommendation systems, social network analyses, bioinformatics, and medical science, are presented.
  arXiv  Detail & Related papers  (2022-11-23T11:31:11Z)
• Graph-based Semi-supervised Local Clustering with Few Labeled Nodes [6.493238575291165]
  Local clustering aims at extracting a local structure inside a graph without the necessity of knowing the entire graph structure. We propose a new semi-supervised local clustering approach using only few labeled nodes.
  arXiv  Detail & Related papers  (2022-11-20T22:55:07Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
  In this paper, we study two important such network analysis techniques, namely, centrality and clustering. An information-flow based model is adopted for clustering, which itself builds upon an information theoretic measure for computing centrality. Our clustering naturally inherits the flexibility to accommodate edge directionality, as well as different interpretations and interplay between edge weights and node degrees.
  arXiv  Detail & Related papers  (2021-11-23T03:01:29Z)
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
  Graph signal processing (GSP) provides a powerful framework for analyzing signals arising in a variety of domains. We propose a novel regularized partial least squares method which both incorporates the observed graph structures and imposes sparsity in order to reflect the underlying block community structure.
  arXiv  Detail & Related papers  (2021-04-06T21:52:15Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)

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.