network analysis

Finding Groups with Maximum Betweenness Centrality via Integer Programming with Random Path Sampling

  • Tomas Lagos
  • Oleg A. Prokopyev
  • Alexander Veremyev
    • Categories Approximation Algorithms, Graphs and Matroids, Stochastic Approaches Tags , , , ,

    One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more

    The Stochastic Pseudo-Star Degree Centrality Problem

  • M. Can Camur
  • Thomas C. Sharkey
  • Chrysafis Vogiatzis
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We introduce the stochastic pseudo-star degree centrality problem, which focuses on a novel probabilistic group-based centrality metric. The goal is to identify a feasible induced pseudo-star, which is defined as a collection of nodes forming a star network with a certain probability, such that it maximizes the sum of the individual probabilities of unique assignments … Read more