Community Detection in Online Social Networks
A Differentially Private and Parsimonious Approach
Bibliographic Data
| ID | 22107494 |
|---|---|
| Authors | Tianxi Ji (0000-0002-9083-5452, Case Western Reserve University), Changqing Luo (0000-0002-6776-7519, Virginia Commonwealth University), Yifan Guo (0000-0001-9897-1312, Case Western Reserve University), Qianlong Wang (0000-0002-3011-0580, Case Western Reserve University), Lixing Yu (0000-0003-0333-2476, Case Western Reserve University), Pan Li (0000-0002-0316-0355, Case Western Reserve University) |
| Year | 2020 |
| Volume | 7 |
| Issue | 1 |
| Pages | 151-163 |
| Publication date | 2020-02-01 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | IEEE Transactions on Computational Social Systems (JOURNAL) |
| Journal identifiers | ISSN: 2329-924X • E-ISSN: 2373-7476 |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) (PUBLISHER) |
| DOI | 10.1109/tcss.2019.2957795 |
| OpenAlex | W3006156162 |
| ISBN | 9781728135205 |
| Language | EN |
| Citations received | 3 |
| References cited | 34 |
Community detection is an effective approach to unveil relationships among individuals in online social networks. In the literature, quite a few algorithms have been proposed to conduct community detection by exploiting the topology of social networks and the attributes of social actors. In practice, community detection is usually conducted by third parties, such as advertisement companies and hospitals, with access to social networks for different purposes, which can easily lead to a privacy breach. In this paper, we investigate community detection in social networks aiming to protect the privacy of both the network topology and the users' attributes. We show that with additional prior knowledge, community detection can be performed by querying the information of only a fraction of instead of the entire population. In particular, we first propose a new scheme called differentially private community detection (DPCD). DPCD detects communities in social networks via a probabilistic generative model, which can be decomposed into subproblems solved by individual users. The private social relationships and attributes of each user are protected by objective perturbation with differential privacy guarantees. Then, we propose a parsimonious node affiliation recovery (NAR) algorithm, which is also differentially private, to unveil the community affiliation information of the whole population based on that of the limited number of queried individuals by solving a sparse optimization problem. Through both theoretical analysis and experimental validation using synthetic and real-world social networks, we demonstrate that the proposed DPCD scheme detects social communities under the modest privacy budget. In addition, we show the effectiveness of NAR to perform community detection by querying a limited number of individuals in social networks
Computer network · Computer security · Data mining · Data science · Differential privacy · Internet privacy · Machine learning · Network topology · Population · Private information retrieval · Probabilistic logic · Social media · Sociology · World Wide Web · Complex Network Analysis Techniques · Computer Science · Engineering · Internet Traffic Analysis and Secure E-voting · Mathematics · Privacy-Preserving Technologies in Data · Artificial Intelligence
| Citations per year | 0.5 |
|---|---|
| Citation span | 2020 - 2024 (5) |
| Highly cited | No |