Budget-Constrained Ego Network Extraction With Maximized Willingness

Many large-scale machine learning approaches and graph algorithms are proposed recently to address a variety of problems in online social networks (OSNs). To evaluate and validate these algorithms and models, the data of ego-centric networks (ego networks) are widely adopted. Therefore, effectively extracting large-scale ego networks from OSNs becomes an important issue, particularly when privacy policies become increasingly strict nowadays. In this paper, we study the problem of extracting ego network data by considering jointly the user willingness, crawling cost, and structure of the network. We formulate a new research problem, named <i>Structure and Willingness Aware Ego Network Extraction (SWAN)</i> and analyze its NP-hardness. We first propose a <inline-formula><tex-math notation="LaTeX">$(1-\frac{1}{e})$</tex-math></inline-formula>-approximation algorithm, named <i>Tristar-Optimized Ego Network Identification with Maximum Willingness (TOMW)</i>. In addition to the deterministic approximation algorithm, we also propose to automatically <i>learn</i> an effective heuristic approach with machine learning, to avoid the huge efforts for human to devise a good algorithm. The learning approach is named <i>Willingness-maximized and Structure-aware Ego Network Extraction with Reinforcement Learning (WSRL)</i>, in which we propose a novel constrastive learning strategy, named <i>Contrastive Learning with Performance-boosting Graph Augmentation</i>. We recruited 1,810 real-world participants and conducted an evaluation study to validate our problem formulation and proposed approaches. Moreover, experimental results on real social network datasets show that the proposed approaches outperform the other baselines significantly.