Reducing Graph Structural Bias by Adding shortcut edges

Algorithms that tackle the problem of minimizing average/maximum hitting time (BMAH/BMMH) between different social network groups, given fixed shortcut edges. The contributions include(1) Proofs that BMAH problem is supermodular. (2) A 1+eps approximation algorithm using the greedy bicriteria method, which improved upon previous studies. (3) Speed up the greedy algorithm by sampling bounded-length absorbing random walks with high probability. (4) A 2+eps approximation factor for the greedy bicriteria algorithm with fast estimation. (5) Stablished a tight upper bound of BMMH using BMAH, which enabled us to derive an approximation algorithm for BMMH based on the results obtained for BMAH. (6) Stablished a connection between BMMH and the asymmetric k-median problem, which led to an approximation guarantee.

Data and Resources
To access the resources you must log in
  • Social network datasetData

    dataset used in the experiments

    The resource: 'Social network dataset' is not accessible as guest user. You must login to access it!
Additional Info
Field Value
Accessibility Virtual Access
AccessibilityMode OnLine Access
Availability On-Line
Basic rights Making available to the public
CreationDate 2023-06-23 20:00
Creator Honglian, Wang,,
External Identifier
Field/Scope of use Research only
Group Social Impact of AI and explainable ML
Group Societal Debates and Misinformation
Owner Honglian, Wang,,
Sublicense rights No
Territory of use World Wide
Thematic Cluster Social Data [SD]
Thematic Cluster Social Network Analysis [SNA]
system:type Method
Management Info
Field Value
Author Wang Honglian
Maintainer Wang Honglian
Version 1
Last Updated 8 September 2023, 14:40 (CEST)
Created 23 June 2023, 20:55 (CEST)