research-article

Mining Signed Networks: Theory and Applications: Tutorial proposal for the Web Conference 2020

Authors:

Aristides Gionis,

Antonis Matakos,

Bruno Ordozgoiti,

Han XiaoAuthors Info & Claims

WWW '20: Companion Proceedings of the Web Conference 2020

Pages 309 - 310

https://doi.org/10.1145/3366424.3383113

Published: 20 April 2020 Publication History

Abstract

Signed networks transform the information encoded by conventional graphs by attaching either a positive or a negative sign to every edge. This subtle modification vastly enhances the modelling capabilities of graphs. For instance, in a social network, where edges might represent interactions between users, the sign may determine whether an exchange was friendly or hostile. However, the introduction of edge signs invalidates many established methods and results from the graph-mining toolbox, and thus, problem formulations and algorithmic techniques must be studied anew. In this tutorial we aim to provide an overview of the literature in mining signed networks. We will present the most important theoretical results since their inception to the present day, we will discuss some of the most common applications, and we will reflect on emerging applications and directions for future work.

References

[1]

Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo. 2019. Discovering Polarized Communities in Signed Networks. arXiv preprint arXiv:1910.02438(2019).

[2]

Jose Cadena, Anil Kumar Vullikanti, and Charu C Aggarwal. 2016. On dense subgraphs in signed network streams. In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 51–60.

[3]

Kai-Yang Chiang, Nagarajan Natarajan, Ambuj Tewari, and Inderjit S Dhillon. 2011. Exploiting longer cycles for link prediction in signed networks. In Proceedings of the 20th ACM international conference on Information and knowledge management. ACM, 1157–1162.

Digital Library

[4]

Kai-Yang Chiang, Joyce Jiyoung Whang, and Inderjit S Dhillon. 2012. Scalable clustering of signed networks using balance normalized cut. In Proceedings of the 21st ACM international conference on Information and knowledge management. ACM, 615–624.

Digital Library

[5]

Lingyang Chu, Zhefeng Wang, Jian Pei, Jiannan Wang, Zijin Zhao, and Enhong Chen. 2016. Finding gangs in war from signed networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1505–1514.

Digital Library

[6]

Fan Chung, Alexander Tsiatas, and Wensong Xu. 2013. Dirichlet pagerank and ranking algorithms based on trust and distrust. Internet Mathematics 9, 1 (2013), 113–134.

[7]

Tyler Derr, Yao Ma, and Jiliang Tang. 2018. Signed graph convolutional networks. In 2018 IEEE International Conference on Data Mining (ICDM). IEEE, 929–934.

[8]

Ming Gao, Ee-Peng Lim, David Lo, and Philips Kokoh Prasetyo. 2016. On detecting maximal quasi antagonistic communities in signed graphs. Data mining and knowledge discovery 30, 1 (2016), 99–146.

[9]

Frank Harary. 1953. On the notion of balance of a signed graph.Michigan Math. J. 2, 2 (1953), 143–146. https://doi.org/10.1307/mmj/1028989917

[10]

Yao Ping Hou. 2005. Bounds for the Least Laplacian Eigenvalue of a Signed Graph. Acta Mathematica Sinica 21, 4 (01 Aug 2005), 955–960.

[11]

Cho-Jui Hsieh, Kai-Yang Chiang, and Inderjit S Dhillon. 2012. Low rank modeling of signed networks. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 507–515.

Digital Library

[12]

Jinhong Jung, Woojeong Jin, Lee Sael, and U Kang. 2016. Personalized ranking in signed networks using signed random walk with restart. In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 973–978.

[13]

Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. 2018. Side: representation learning in signed directed networks. In Proceedings of the 2018 World Wide Web Conference. 509–518.

Digital Library

[14]

Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. 2016. Edge weight prediction in weighted signed networks. In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 221–230.

[15]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web. ACM, 641–650.

Digital Library

[16]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed Networks in Social Media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (Atlanta, Georgia, USA) (CHI ’10). ACM, New York, NY, USA, 1361–1370. https://doi.org/10.1145/1753326.1753532

Digital Library

[17]

Jiliang Tang, Charu Aggarwal, and Huan Liu. 2016. Recommendations in signed social networks. In Proceedings of the 25th International Conference on World Wide Web. 31–40.

Digital Library

[18]

J.H. van Lint and J.J. Seidel. 1966. Equilateral point sets in elliptic geometry. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen: Series A: Mathematical Sciences 69, 3 (1966), 335–348.

[19]

Suhang Wang, Jiliang Tang, Charu Aggarwal, Yi Chang, and Huan Liu. 2017. Signed network embedding in social media. In Proceedings of the 2017 SIAM international conference on data mining. SIAM, 327–335.

[20]

Zhaoming Wu, Charu C Aggarwal, and Jimeng Sun. 2016. The troll-trust model for ranking in signed networks. In Proceedings of the Ninth ACM international conference on Web Search and Data Mining. ACM, 447–456.

Digital Library

Cited By

Chen MJiang WPan YDai JLei YJi C(2022)SGFNNs: Signed Graph Filtering-based Neural Networks for Predicting Drug–Drug InteractionsJournal of Computational Biology10.1089/cmb.2022.011329:10(1104-1116)Online publication date: 1-Oct-2022
https://doi.org/10.1089/cmb.2022.0113
Chen MPan YJi C(2021)Predicting Drug Drug Interactions by Signed Graph Filtering-Based Convolutional NetworksBioinformatics Research and Applications10.1007/978-3-030-91415-8_32(375-387)Online publication date: 18-Nov-2021
https://doi.org/10.1007/978-3-030-91415-8_32
Tzeng ROrdozgoiti BGionis ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Discovering conflicting groups in signed networksProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496645(10974-10985)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496645

Index Terms

Mining Signed Networks: Theory and Applications: Tutorial proposal for the Web Conference 2020
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

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 ...
Balance in Signed Bipartite Networks
CIKM '19: Proceedings of the 28th ACM International Conference on Information and Knowledge Management

A large portion of today's big data can be represented as networks. However, not all networks are the same, and in fact, for many that have additional complexities to their structure, traditional general network analysis methods are no longer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '20: Companion Proceedings of the Web Conference 2020

April 2020

854 pages

ISBN:9781450370240

DOI:10.1145/3366424

Editors:
Amal El Fallah Seghrouchni
Sorbonne University, France
,
Gita Sukthankar
University of Central Florida, United States
,
Tie-Yan Liu
Microsoft Research Asia, China
,
Maarten van Steen
University of Twente, Netherlands

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '20

Sponsor:

SIGWEB

WWW '20: The Web Conference 2020

April 20 - 24, 2020

Taipei, Taiwan

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen MJiang WPan YDai JLei YJi C(2022)SGFNNs: Signed Graph Filtering-based Neural Networks for Predicting Drug–Drug InteractionsJournal of Computational Biology10.1089/cmb.2022.011329:10(1104-1116)Online publication date: 1-Oct-2022
https://doi.org/10.1089/cmb.2022.0113
Chen MPan YJi C(2021)Predicting Drug Drug Interactions by Signed Graph Filtering-Based Convolutional NetworksBioinformatics Research and Applications10.1007/978-3-030-91415-8_32(375-387)Online publication date: 18-Nov-2021
https://doi.org/10.1007/978-3-030-91415-8_32
Tzeng ROrdozgoiti BGionis ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Discovering conflicting groups in signed networksProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496645(10974-10985)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496645

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents