research-article

Stable Community Detection in Signed Social Networks

Authors:

Xun WangAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 34, Issue 10

Pages 5051 - 5055

https://doi.org/10.1109/TKDE.2020.3047224

Published: 01 October 2022 Publication History

Abstract

Community detection is one of the most fundamental problems in social network analysis, while most existing research focuses on unsigned graphs. In real applications, social networks involve not only positive relationships but also negative ones. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq1-3047224.gif"/></alternatives></inline-formula>-core, to measure the stability of a community in signed graphs. The stable <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq2-3047224.gif"/></alternatives></inline-formula>-core model not only emphasizes user engagement, but also eliminates unstable structures. We show that the problem of finding the maximum stable <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq3-3047224.gif"/></alternatives></inline-formula>-core is NP-hard. To scale for large graphs, novel pruning strategies and searching methods are proposed. We conduct extensive experiments on 6 real-world signed networks to verify the efficiency and effectiveness of proposed model and techniques.

References

[1]

S. B. Seidman, “Network structure and minimum degree,” Soc. Netw., vol. 5, pp. 269–287, 1983.

[2]

Y. Zhang, J. X. Yu, Y. Zhang, and L. Qin, “A fast order-based approach for core maintenance,” in Proc. IEEE 33rd Int. Conf. Data Eng., 2017, pp. 337–348.

[3]

F. Morone, G. Ferraro, and H. A. Makse, “The k-core as a predictor of structural collapse in mutualistic ecosystems,” Nat. Phys., vol. 15, pp. 95–102, 2019.

[4]

J. Tang, Y. Chang, C. Aggarwal, and H. Liu, “A survey of signed network mining in social media,” ACM Comput. Surv., vol. 49, 2016, Art. no.

[5]

D. Cartwright and F. Harary, “Structural balance: A generalization of heider's theory,” Psychol. Rev., vol. 63, pp. 277–93, 1956.

[6]

R. Figueiredo and Y. Frota, “The maximum balanced subgraph of a signed graph: Applications and solution approaches,” Eur. J. Oper. Res., vol. 236, pp. 473–487, 2014.

[7]

B. Ordozgoiti, A. Matakos, and A. Gionis, “Finding large balanced subgraphs in signed networks,” in Proc. Web Conf., 2020, pp. 1378–1388.

[8]

F. Bonchi, E. Galimberti, A. Gionis, B. Ordozgoiti, and G. Ruffo, “Discovering polarized communities in signed networks,” in Proc. 28th ACM Int. Conf. Inf. Knowl. Manage., 2019, pp. 961–970.

[9]

H. Xiao, B. Ordozgoiti, and A. Gionis, “Searching for polarization in signed graphs: A local spectral approach,” in Proc. Web Conf., 2020, pp. 362–372.

[10]

C. Giatsidis, B. Cautis, S. Maniu, D. M. Thilikos, and M. Vazirgiannis, “Quantifying trust dynamics in signed graphs, the s-cores approach,” in Proc. SIAM Int. Conf. Data Mining, 2014, Art. no.

[11]

R.-H. Liet al., “Efficient signed clique search in signed networks,” in Proc. IEEE 34th Int. Conf. Data Eng., 2018, pp. 245–256.

[12]

Y. Zhang, J. X. Yu, Y. Zhang, and L. Qin, “A fast order-based approach for core maintenance,” in Proc. IEEE 33rd Int. Conf. Data Eng., 2017, pp. 337–348.

[13]

W. Zhu, M. Zhang, C. Chen, X. Wang, F. Zhang, and X. Lin, “Pivotal relationship identification: The K-truss minimization problem,” in Proc. 28th Int. Joint Conf. Artif. Intell., 2019, pp. 4874–4880.

[14]

J. Cheng, Y. Ke, A. W.-C. Fu, J. X. Yu, and L. Zhu, “Finding maximal cliques in massive networks,” ACM Trans. Database Syst., vol. 36, 2011, Art. no.

Digital Library

[15]

Z. Zhou, F. Zhang, X. Lin, W. Zhang, and C. Chen, “K-core maximization: An edge addition approach,” in Proc. 28th Int. Joint Conf. Artif. Intell., 2019, pp. 4867–4872.

[16]

J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Signed networks in social media,” in Proc. SIGCHI Conf. Hum. Factors Comput. Syst., 2010, pp. 1361–1370.

[17]

J. Cadena, A. K. Vullikanti, and C. C. Aggarwal, “On dense subgraphs in signed network streams,” in Proc. IEEE 16th Int. Conf. Data Mining, 2016, pp. 51–60.

[18]

D. Li and J. Liu, “Modeling influence diffusion over signed social networks,” IEEE Trans. Knowl. Data Eng., early access, Jul. 23, 2019.

[19]

C. E. Tsourakakis, T. Chen, N. Kakimura, and J. Pachocki, “Novel dense subgraph discovery primitives: Risk aversion and exclusion queries,” in Proc. Joint Eur. Conf. Mach. Learn. Knowl. Discov. Databases, 2019, pp 378–394.

[20]

Z. Chen, L. Yuan, X. Lin, L. Qin, and J. Yang, “Efficient maximal balanced clique enumeration in signed networks,” in Proc. Web Conf., 2020, pp. 339–349.

[21]

M. Latapy, “Main-memory triangle computations for very large (sparse (power-law)) graphs,” Theor. Comput. Sci., vol. 407, pp. 458–473, 2008.

Digital Library

[22]

Y. Fanget al., “A survey of community search over big graphs,” VLDB J., vol. 29, pp. 353–392, 2019.

Digital Library

Cited By

Yang JZhong MZhu YQian TLiu MYu J(2024)Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic ComputationProceedings of the VLDB Endowment10.14778/3681954.368196717:11(2840-2853)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681967
Arya ASerra ESpezzano F(2024)Realistic Synthetic Signed Network Generation and AnalysisProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680274(5439-5442)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680274
Minici MCinus FBonchi FManco GSerra ESpezzano F(2024)Link Polarity Prediction from Sparse and Noisy Labels via Multiscale Social BalanceProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679786(1689-1699)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679786
Show More Cited By

Index Terms

Stable Community Detection in Signed Social Networks
1. Applied computing

Index terms have been assigned to the content through auto-classification.

Recommendations

Degree choosable signed graphs

A signed graph is a graph in which each edge is labeled with +1 or 1. A (proper) vertex coloring of a signed graph is a mapping that assigns to each vertex vV(G) a color (v)Z such that every edge vw of G satisfies (v)(vw)(w), where (vw) is the sign of ...
Homomorphisms of Signed Graphs

A signed graph [G,Σ] is a graph G together with an assignment of signs + and - to all the edges of G where Σ is the set of negative edges. Furthermore [G,Σ1] and [G,Σ2] are considered to be equivalent if the symmetric difference of Σ1 and Σ2 is an edge ...
Identifying the social-balanced densest subgraph from signed social networks

Identifying the dense subgraphs from large graphs is important and useful to various social media mining applications. Most of existing works focus on the densest subgraph problem in the unweighted and undirected represented social network which can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 34, Issue 10

Oct. 2022

502 pages

ISSN:1041-4347

Issue’s Table of Contents

1041-4347 © 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 October 2022

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang JZhong MZhu YQian TLiu MYu J(2024)Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic ComputationProceedings of the VLDB Endowment10.14778/3681954.368196717:11(2840-2853)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681967
Arya ASerra ESpezzano F(2024)Realistic Synthetic Signed Network Generation and AnalysisProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680274(5439-5442)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680274
Minici MCinus FBonchi FManco GSerra ESpezzano F(2024)Link Polarity Prediction from Sparse and Noisy Labels via Multiscale Social BalanceProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679786(1689-1699)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679786
Chung KZhou AWang YChen L(2023)Maximum Balanced (k,ϵ)-Bitruss Detection in Signed Bipartite GraphProceedings of the VLDB Endowment10.14778/3632093.363209917:3(332-344)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632099
Yang FMa HYan CLi ZChang L(2023)Polarized Communities Search via Co-guided Random Walk in Attributed Signed NetworksACM Transactions on Internet Technology10.1145/361344923:4(1-22)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3613449
Yang FMa HYan CLi ZChang LFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Co-guided Random Walk for Polarized Communities SearchProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614814(2949-2958)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3614814
Arya APandey PSaxena A(2023)Balanced and Unbalanced Triangle Count in Signed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327265735:12(12491-12496)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3272657
Sun RWu YWang XChen CZhang WLin X(2023)Clique Identification in Signed Graphs: A Balance Theory Based ModelIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327263635:12(12513-12527)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3272636
Kalimzhanov TKhamseh’i ADadlani AKumar MKhonsari A(2023)Co-Evolution of Viral Processes and Structural Stability in Signed Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.320712335:8(7809-7814)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3207123
Tang ZWang JWu YWang XQin LZhang Y(2023)Balanced Hop-Constrained Path Enumeration in Signed Directed GraphsDatabases Theory and Applications10.1007/978-3-031-47843-7_22(315-328)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-47843-7_22

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents