GitHub repository: HawkinYap/Preserving-Minority-Structures-in-Graph-Sampling
Primary language: Jupyter Notebook
Description: Sampling is a widely used graph reduction technique to accelerate graph computations and simplify graph visualizations. However, we assume that existing graph sampling algorithms cannot effectively preserve minority structures that are important in graph analyses but rarely occurred or small in a graph. In this work, we ﬁrst conduct a pilot user study to investigate representative minority structures that are most appealing to human viewers. We then perform a quantitative analysis to evaluate the performance of existing graph sampling algorithms regarding minority structure preservation. Results conﬁrm our assumption and suggest key points for designing a new graph sampling algorithm named Mino-centric Graph Sampling (MCGS). First, we propose a triangle-detection-based algorithm and a cut-point-based algorithm for fast minority structure identiﬁcation. Second, we establish a set of importance assessment rules to guide the preservation of minority structures. Third, we introduce three optimization objectives into a greedy strategy to balance the preservation between minority and majority structures and suppress the generation of new minority structures. Finally, a series of experiments and case studies are conducted to evaluate the effectiveness of the proposed MCGS.