Launching attacks against community detection to significantly deteriorate its performance has received increasing research attention recently due to the importance and wide applications of community detection. However, we observe that most previous attacks suffer from two major weaknesses: i) the negligence of community structures in their proxy metrics, and ii) limited attack scope. To tackle these issues, we propose a new research problem,Perturbing Community Detection with$\mu$-Triad Minimization ($\mu$-PerCD), based on a new metric proposed in this paper, named$\mu$-triad, to attack community detection more effectively. We first present analysis results to justify the effectiveness of$\mu$-triads by comparing it with many other candidate proxy metrics. Also, we illustrate the rationale behind the formulation of$\mu$-PerCD problem with experiments on real datasets. Then, we analyze the NP-hardness of$\mu$-PerCD and propose two$\frac{1}{4}(1-\frac{1}{e})$-approximation algorithms, named$\mu$-Triad Minimization with Edge Addition ($\mu$MEA)and$\mu$MEA+, where$\mu$MEA+is an efficiency-enhanced version of$\mu$MEAwhile retaining the approximation ratio. Extensive experiments on real datasets demonstrate the effectiveness of the proposed algorithm in attacking various community detection algorithms, significantly outperforming the other state-of-the-art baselines.

A recent line of research on learning to solve graph optimization problems has attracted much research attention. However, most recent machine learning approaches to graph optimization problems usually employ graph generators to randomly generate training graphs, which may lead to overfitting and deteriorate the model's generalization. To tackle this issue, we observe that enhancing the diversity of training graphs is a crucial factor in improving the model's performance. Therefore, in this paper, we formulate a new research problem, named Graph Augmentation for Diversity Maximization (GRAM), to maximize the training graph diversity by performing graph modifications. We first analyze the NP-hardness of GRAM. We then propose a 2-approximation algorithm and formally analyze its performance guarantee. Experimental results on well-known graph optimization problems show that our proposed approach significantly outperforms the baselines, such as graph augmentation and deep learning-based graph generation approaches.

Recently, many machine learning-based approaches that effectively solve graph optimization problems have been proposed. The graph optimization problem is the problem that aims to optimize (maximize or minimize) a quantity that is associated with a graph, such as the Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS) problems. These approaches are usually trained on graphs randomly generated with graph generators or sampled from existing datasets. However, we observe that such training graphs lead to poor testing performance if the testing graphs are not generated analogously, i.e., the generalizability of the models trained on thoserandomly generatedtraining graphs is very limited. To address this critical issue, in this paper, we propose a new framework, namedLearning with Iterative Graph Diversification (LIGD), and formulate a new research problem, namedDiverse Graph Modification Problem (DGMP), that iteratively generate diversified training graphs and train the models that solve graph optimization problems to improve their performance significantly. We propose three approaches to solve DGMP by considering both the performance of the machine learning approaches and the structural properties of the training graphs. In addition, we study a practical case of DGMP, namedDiverse Graph Modification Problem with XOR Diversity (DGMP-XDiv), which considers an XOR-based diversity function. We propose a polynomial-time algorithm namedStructure Diversifying Modification on Edge Score (DMES)to obtain the optimal solution. We also proposeDMES with Efficiency-Boosting Strategies (DMES-EB)to enhance the efficiency of DMES significantly. Experimental results on well-known problems show that our proposed approaches significantly boost the performance of both supervised and reinforcement learning approaches. They produce near-optimal results and significantly outperform the baseline approaches, such as graph augmentation and diffusion-based approaches.

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, namedStructure and Willingness Aware Ego Network Extraction (SWAN)and analyze its NP-hardness. We first propose a$(1-\frac{1}{e})$-approximation algorithm, namedTristar-Optimized Ego Network Identification with Maximum Willingness (TOMW). In addition to the deterministic approximation algorithm, we also propose to automaticallylearnan effective heuristic approach with machine learning, to avoid the huge efforts for human to devise a good algorithm. The learning approach is namedWillingness-maximized and Structure-aware Ego Network Extraction with Reinforcement Learning (WSRL), in which we propose a novel constrastive learning strategy, namedContrastive Learning with Performance-boosting Graph Augmentation. 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.

Egocentric network (ego network) data are very important for evaluating algorithms and machine learning approaches in Online Social Networks (OSNs). Nevertheless, obtaining the ego network data from OSNs is not a trivial task. Conventional manual approaches are time-consuming, and sometimes the ego network data are quite incomplete because only a small number of users would agree to provide their data. This is because there are two important factors that should be considered simultaneously for this data acquisition task: i) users’ willingness to provide their data, and ii) the structure of the ego network. However, addressing the above two factors to obtain the more complete ego network data has not received much research attention. Therefore, in this paper, we address this issue by proposing a family of new research problems. The first proposed problem, namedWillingness Maximization for Ego Network Extraction in Online Social Networks (WMEgo), identifies a set of ego networks from a single OSN, such that the willingness of the users to provide their data is maximized. We prove that WMEgo is NP-hard and propose a$\frac{1}{2}(1-\frac{1}{e})$-approximation algorithm, namedEgo Network Identification with Maximum Willingness (EIMW). Furthermore, we extend the idea of WMEgo to multiple social networks and formulate a new research problem, namedWillingness Maximization on Multiple Social Networks for Ego Network Extraction (WM$^{2}$2Ego), which is able to effectively obtain ego network data from multiple social networkssimultaneously. We propose a$\frac{1}{2}$-approximation algorithm, namedMaximum Expansion forUNifiedEXpenses (MUNEX)for a special case of WM$^{2}$Ego and then design a constant-ratio approximation algorithm to the general WM$^{2}$Ego problem, namedMaximum Expansion with Expense Examination (M3E). We conduct two evaluation studies with 672 and 1,052 volunteers to validate the proposed WMEgo and WM$^{2}$Ego problems, respectively, and show that they are able to obtain much more complete ego network data compared to other baselines. We also perform extensive experiments on multiple real datasets to demonstrate that the proposed approaches significantly outperform the other baselines.

According to the literature in psychology, the existence of small dense subgroups is closely related to many mental illnesses, such as depression, bullying, and psychotic disorders. Here, small dense subgroups refer to the small groups in the social network in which members are socially dense but have no or few links to other individuals outside the group. Therefore, in this article, we make the first attempt to address the issue of small dense subgroups with the concept of network intervention from Psychology. We first introduce the new notion of Δ-Subgroups (Δ-SGs) to quantify the small dense subgroups. Then, following the concept of network intervention, we formulate a new research problem, Small Subgroup Maximum Reduction Problem (SSMP), to reduce the number of small dense subgroups (i.e., Δ-SGs) in the social network. We prove that SSMP is NP-Hard and propose a linear-time algorithm, namely 3-SMMTG, to find the optimal solution for a special case of SSMP with = 3Δ=3. We then devise a 1/2(1-1/e)-approximation algorithm, namely ESGR, for the general SSMP and enhance its efficiency with effective pruning methods. We conduct a 8-week evaluation study with 812 participants to validate the proposed SSMP and ESGR. The results show that the participants with the network intervention recommended by ESGR have significant improvements on Internet addiction and depression, as compared to those individuals without any intervention. We also perform experiments on 7 real datasets, and the experimental results manifest that the proposed algorithms outperform the other baselines in both efficiency and solution quality.

The data of egocentric networks (ego networks) are very important for evaluating and validating the algorithms and machine learning approaches in Online Social Networks (OSNs). Nevertheless, obtaining the ego network data from OSNs is not a trivial task. Conventional manual approaches are time-consuming, and only a small number of users would agree to contribute their data. This is because there are two important factors that should be considered simultaneously for this data acquisition task: i) users' willingness to contribute their data, and ii) the structure of the ego network. However, addressing the above two factors to obtain the more complete ego network data has not received much research attention. Therefore, in this paper, we make our first attempt to address this issue by proposing a new research problem, named Willingness Maximization for Ego Network Extraction in Online Social Networks (WMEgo), to identify a set of ego networks from the OSN such that the willingness of the users to contribute their data is maximized. We prove that WMEgo is NP-hard and propose a 1/2*(1 1/e)-approximation algorithm, named Ego Network Identification with Maximum Willingness (EIMW). We conduct an evaluation study with 672 volunteers to validate the proposed WMEgo and EIMW, and perform extensive experiments on multiple real datasets to demonstrate the effectiveness and efficiency of our approach.