Source-linked AI summary
A Survey of Signed Network Mining in Social Media
Jiliang Tang, Yi Chang, Charu Aggarwal, Huan Liu
TL;DR
Signed-network mining must account for positive and negative relations in increasingly large, sparse, and noisy social-media data. This survey synthesizes signed-network concepts and social theories, organizes mining tasks, reviews representative algorithms, and identifies underexplored directions. It finds recurring use of balance and status theories alongside random walks, low-rank approximation, and spectral clustering across tasks.
Problem
Large-scale social-media signed networks create mining challenges and opportunities that cannot be addressed by simply extending unsigned-network methods.
Method
The survey reviews signed-network representations, properties, social theories, mining tasks, representative algorithms, and formal research directions for underexplored tasks.
Results
Balance and status theories are widely used through feature engineering, constraint generation, and objective definition, while random walks, low-rank approximation, and spectral clustering recur across mining tasks.
Takeaways & Limitations
Signed-network mining is an early-stage field with well-studied and insufficiently investigated task categories requiring continued research.
Takeaways & Limitations
The survey assumes readers understand basic social-network analysis, data-mining, machine-learning, and optimization techniques.
Abstract
from arXiv · showhide
Many real-world relations can be represented by signed networks with positive and negative links, as a result of which signed network analysis has attracted increasing attention from multiple disciplines. With the increasing prevalence of social media networks, signed network analysis has evolved from developing and measuring theories to mining tasks. In this article, we present a review of mining signed networks in the context of social media and discuss some promising research directions and new frontiers. We begin by giving basic concepts and unique properties and principles of signed networks. Then we classify and review tasks of signed network mining with representative algorithms. We also delineate some tasks that have not been extensively studied with formal definitions and also propose research directions to expand the field of signed network mining.
1. INTRODUCTION
Signed network mining extends longstanding theories of positive and negative relations to large-scale, sparse, noisy social-media data. This survey reviews the field’s foundations, organizes mining tasks, and identifies underexplored problems and research directions.
- Foundations: Signed networks represent social relations with both positive and negative links, grounding a research tradition that spans social psychology, physics, and computer science.Structural balance theory and balanced signed graphs characterize important patterns in these networks.
- Motivation: Large-scale, sparse, and noisy social-media networks shifted signed-network research from theory and measurement toward data mining and machine learning.Earlier physical-world networks were typically small, dense, and clean.
- Motivation: Negative links require dedicated methods because unsigned-network concepts and algorithms may not transfer directly to signed networks.Signed networks introduce distinct negative-link topology and collective properties with positive links.
- Research gaps: The field’s task development is highly imbalanced: some areas are extensively studied, whereas others still need further investigation.The survey aims to clarify the state of the art and enrich research on insufficiently studied tasks.
- Scope: The survey covers signed-network representations, negative-link topology, and joint positive-negative properties informed by social theories.These foundations support the review of mining tasks and algorithms.
- Organization: Mining tasks are classified into node-oriented, link-oriented, and application-oriented categories, with representative algorithms reviewed for well-studied tasks.The survey also gives formal definitions and promising directions for tasks that remain insufficiently investigated.
2. BASIS OF SIGNED NETWORKS
Signed networks require representations and mining principles that preserve the distinct roles of positive and negative links. Their structural properties and social-theory foundations differ across link types and support balance- and status-oriented analysis.
- Network Representation: A signed network can be represented with one adjacency matrix encoding positive, negative, and missing links as 1, −1, and 0.Alternatively, positive and negative links can be represented separately with two adjacency matrices, with A = Ap − An and Ap = (|A| + A) / 2.
- Properties of Negative Networks: Positive links are denser than negative links, while users with negative links also exhibit power-law degree distributions.Many users have no incoming or outgoing negative links; among users with negative links, most have few and a few have many.
- Properties of Negative Networks: Negative-link networks have lower clustering coefficients and reciprocity than positive-link networks, limiting the direct transfer of properties such as triadic closure.Negative links also show weaker reciprocity and greater asymmetry between incoming and outgoing degrees.
- Properties of Negative Networks: Negative links may not be transitive and may denote neither similarity nor dissimilarity, unlike positive links’ stronger transitivity and similarity correlations.Studies observed both “enemies’ enemies are friends” and “enemies’ enemies are enemies,” while negative-linked users were more similar than users without links but less similar than positive-linked users.
- Social Theories: Balance theory characterizes compatible sign patterns, while status theory applies to directed networks by interpreting positive and negative links as status relations.Balance theory concerns cycles or triads, whereas status theory defines higher status through incoming positive or outgoing negative links.
Balance Theory✓
Signed-network mining builds on balance and status theories while using social-media datasets and organizing tasks by nodes, links, and applications. The survey notes that these task categories are unevenly studied.
- Balance Theory: More than 90% of triads in typical social-media signed networks satisfy status theory.The survey examines all 12 triad types and computes the ratio satisfying status theory.
- Balance Theory: Status theory and balance theory can disagree: some triads satisfy one theory, both theories, or neither.The survey applies balance theory to directed signed networks by ignoring link directions.
- Popular Data Sets for Benchmarking: Epinions and Slashdot provide widely used signed-social-network datasets for benchmarking analytical algorithms.Epinions contains trust and distrust links, while Slashdot contains friend and foe links.
- Tasks of Mining Signed Networks: Mining tasks are categorized as node-oriented, link-oriented, and application-oriented, with uneven development across categories.Some tasks are well studied, whereas others require further investigation.
3. NODE-ORIENTED TASKS
Node-oriented signed-network mining includes node ranking, community detection, node classification, and node embedding. Ranking and community detection are extensively studied, whereas classification and embedding need further investigation.
- 3. NODE-ORIENTED TASKS: Node-oriented tasks include node ranking, community detection, node classification, and node embedding.The survey reviews representative algorithms for these tasks, focusing on ranking and community detection.
- 3. NODE-ORIENTED TASKS: Node classification and node embedding are identified as node-oriented tasks needing further investigation.Node ranking and community detection are described as extensively studied.
3.1. Node Ranking
Signed-network node ranking orders users by exploiting both positive and negative links. Surveyed approaches extend centrality, PageRank, and HITS-style methods to account for signed relations.
- 3.1. Node Ranking: Node ranking orders users by exploiting network structure while considering both positive and negative links.Unsigned-network ranking methods generally cannot directly handle negative values.
- Centrality-based Algorithms: Centrality-based methods assign prestige using positive and negative incoming-link counts, with related approaches subtracting negative from positive indegree.Eigenvector centrality can also reveal clique structure and status in balanced complete signed networks.
- PageRank-based Algorithms: PageRank-based methods handle signs through separate positive and negative scores, modified random walks, or mechanisms that avoid negative links.One approach computes separate scores and differences, while another modifies walks so negatively connected nodes are visited less.
- PageRank-based Algorithms: Within a certain range of µ, one signed PageRank formulation achieves a global solution from arbitrary initializations.The result is stated for the iterative status-score formulation.
- HITS-based Algorithms: HITS-based methods either run HITS separately on positive and negative networks or incorporate link signs directly.Related work replaces hub and authority with bias and deserve, representing trustworthiness and prestige.
3.2. Community Detection in Signed Networks
Signed community detection seeks groups with positive links within communities and negative links between them. The survey reviews clustering, spectral, modularity, mixture-model, and dynamic approaches.
- 3.2. Community Detection in Signed Networks: Signed community detection identifies groups densely connected by positive links internally and negative links between groups.This differs substantially from unsigned community detection because negative links alter the community definition.
- Clustering-based Algorithms: k-balanced social-theory algorithms minimize positive links between clusters and negative links inside clusters.A related objective uses E = αNn + (1 −α)Np and optimizes it through node reallocation or simulated annealing.
- Clustering-based Algorithms: The clustering objective E = αNn + (1 −α)Np penalizes negative links within clusters and positive links between clusters.Here, Nn counts negative intracluster links and Np counts positive intercluster links.
- Spectral Clustering: Signed spectral methods use Laplacian matrices to detect positive-link clusters and separate negatively linked pairs.The signed Laplacian is positive-definite if and only if the network is unbalanced.
- Modularity-based Algorithms: Signed modularity balances positive links that form communities against negative links that disrupt them.Its stated properties include reducing to positive modularity without negative links and equaling zero when all nodes share one community.
- Mixture-model-based Algorithms: Mixture-model methods provide soft partitions and memberships, enabling detection of overlapping communities in signed networks.The signed probabilistic mixture model generates positive links within communities and negative links across different communities.
3.3. Promising Directions for Node-oriented Tasks
Node-oriented signed-network research focuses on classification and embedding, where positive and negative links require dedicated modeling choices. Promising directions include adapting unsigned methods and developing models that capture signed-network properties and multiple views.
- Node Classification in Signed Networks: Node classification in signed networks infers labels for unlabeled users using positive links, negative links, and observed labels.
- Node Classification in Signed Networks: Research can adapt algorithms from unsigned networks or develop novel models based on signed-network semantics.
- Node Classification in Signed Networks: A proposed framework captures single-view and multi-view information from signed networks for node classification.
- Node Embedding: Signed-network embedding learns low-dimensional vector representations for users, but existing work remains limited compared with unsigned-network embedding.
- Node Embedding: Embedding methods require an objective function for signed networks and an algorithm to optimize that objective.
4. LINK-ORIENTED TASKS
Link-oriented tasks analyze relationships between nodes, extending unsigned-network problems and introducing signed-specific tasks. The survey distinguishes link prediction from sign prediction and reviews supervised and unsupervised approaches based on features, similarity, propagation, and low-rank structure.
- Overview: Link-oriented tasks study links among nodes, including link prediction, tie-strength prediction, sign prediction, and negative link prediction.
- Link Prediction and Sign Prediction: Link prediction infers new positive and negative links from existing signed links, whereas sign prediction infers signs for existing links.
- Link Prediction: Supervised link-prediction methods treat link existence as labels and construct features for user pairs.
- Supervised Methods: Feature construction can use signed degrees, balance-theory triangles, ego-network patterns, and user attributes.
- Unsupervised Methods: Unsupervised methods use similarity, propagation, or low-rank approximation to infer link signs from signed-network structure.
- Similarity-based Methods: Similarity-based methods first calculate node similarity and then aggregate signs from similar nodes or signed triplets.
- Low-rank Approximation Methods: Low-rank methods use weak structural balance to motivate low-rank models that approximate the signed adjacency matrix.
4.2. Sign Prediction
Sign prediction infers signs for existing links in unsigned social networks, where topology alone is generally insufficient. The survey reviews theory-based, cross-media, interaction-based, and sentiment-based sources, while distinguishing this task from negative-link prediction and tie-strength prediction.
- Definition and Motivation: Sign prediction infers positive or negative signs for existing links in a given unsigned network.
- Definition and Motivation: Predicting signs from an unsigned network alone is difficult, so existing predictors use additional information sources.
- Sign Prediction Methods: Balance theory and status theory provide latent-factor models for representing user relationships and predicting link signs.
- Sign Prediction Methods: Cross-media information can transfer latent topological features from a source network to predict signs in a target unsigned network.
- Negative Link Prediction: Negative links are valuable for analytical tasks but are generally not explicitly collected by major social-media services.
- Negative Link Prediction: Negative-link prediction identifies node pairs likely to form negative links, unlike sign prediction, which labels already existing links.
- Negative Link Prediction: Interaction data can predict negative links through correlations between negative interactions and negative links, with reported generalization across social-media sites.
- Tie Strength Prediction: Tie-strength prediction assigns continuous strengths to positive and negative relations rather than only binary signs.
5. APPLICATION-ORIENTED TASKS
Application-oriented tasks augment traditional social-media mining algorithms with signed-network information. Signed networks can supplement existing applications such as recommendation.
- Application-oriented Tasks: Application-oriented tasks augment traditional algorithms with signed-network information for applications including recommendation.
5.1. Recommendation with Signed Networks
Signed-network recommendation methods extend collaborative filtering by incorporating positive and negative social links through memory-based and model-based approaches. These methods use negative links as exclusions, dissimilarities, propagated signals, or constraints on latent factors.
- Memory-based Methods: Memory-based methods predict missing ratings by aggregating ratings from similar users, with connection strength determining peer influence.User similarity may use Pearson correlation or cosine similarity.
- Memory-based Methods: Negative links can exclude unwanted users, act as negative weights, or be incorporated after propagating positive and negative values.These strategies respectively avoid recommendations, represent dissimilarity, or reduce the influence of negative values.
- Model-based Methods: Model-based methods commonly use matrix factorization, modeling ratings through interactions between user preference and item characteristic latent factors.The optimization includes regularization to control model fit and overfitting.
- Model-based Methods: Negative-link modeling may maximize latent-factor distance, treating negative links as dissimilarity measurements.This approach is optimized with gradient descent to obtain a local minimum.
- Model-based Methods: Recent work instead models signed relationships comparatively: positively linked users should be more similar than users connected by negative links.This reflects evidence that negatively linked users can be more similar than randomly selected pairs, while positive links indicate greater similarity.
5.2. Information Diffusion
Signed-network information diffusion extends established diffusion models by representing how positive and negative ties affect adoption, opinion, and activation. Reviewed approaches include voter, SIR, independent-cascade, and threshold-based models.
- Overview: Signed-network diffusion builds on unsigned-network models including voter, SIR, independent cascade, and threshold models.These models provide established frameworks for studying information spread and dynamical processes.
- Voter Model: 38% and 21% more influence is generated at maximum by the signed voter model than by the positive-links-only model on the Epinions dataset.The reported gains are dataset-specific and concern maximum influence.
- Voter Model: Signed voter models represent two opposing opinions, with users more likely to adopt friends’ opinions and foes’ opposite opinions.The model studies opinion switching according to signed interactions.
- SIR Model: Signed SIR variants define five states, extending the standard model’s susceptible, infected, and recovered states for signed-network diffusion.The supplied passage introduces the five-state formulation but does not enumerate all five states.
- Independent Cascade Model: The polarity-related cascade model uses negative, positive, and inactive states, with activation state determined by the activating user’s state and link sign.It also limits each user to one activation per step.
- Threshold Model: A signed threshold model assigns payoff matrices to nodes and reduces to the standard threshold model when all payoff matrices are identical.Nodes begin with behavior B, while randomly selected nodes change to behavior A.
5.3. Promising Directions for Application-oriented Tasks
Signed-network application research extends classification and clustering by combining user-generated content, authorship, attributes, labels, and signed user-user links. The survey identifies negative links as additional information and constraints for these tasks.
- Application-oriented Tasks: Signed-network applications can extend established unsigned-network tasks such as data classification, clustering, propagation, recommendation, sentiment analysis, and feature selection.The section focuses on application-oriented tasks involving user-generated data.
- Data Classification: Data classification predicts class labels for unseen posts using post features, authorship information, and user-user or user-post links.The formulation represents authorship with P, post attributes with X, and labels with Y.
- Data Classification: Unsigned-network classification exploits label consistency among posts from the same user and similarity among posts from linked users.One approach converts contextual information into correlation links between posts.
- Data Clustering: Data clustering seeks k post clusters using X, P, and A without available label information.The clustering function maps these inputs to clusters C1 through Ck.
- Data Clustering: Negative links may indicate that posts come from different clusters and can serve as additional clustering constraints.The survey also identifies pseudo-label transformation from clustering to classification as a research direction.
6. CONCLUSIONS
The survey organizes signed-network mining into node-, link-, and application-oriented tasks, reviewing established algorithms alongside underexplored problems and research directions. It finds recurring use of social theories and computational techniques across tasks.
- Conclusions: The survey classifies signed-network mining tasks into node-oriented, link-oriented, and application-oriented groups.For each group, it reviews representative algorithms and formalizes insufficiently studied tasks with research directions.
- Methodological Perspective: Balance theory and status theory are applied through feature engineering, constraint generating, and objective defining.These mechanisms connect social theories to computational models across mining tasks.
- Methodological Perspective: Feature engineering extracts theory-based features, constraint generating adds theory-based constraints, and objective defining embeds theories in model objectives.Examples include triangle or triad features, regularization terms, and balance- or status-based objectives.
- Technique Perspective: Random walk, low-rank approximation, and spectral clustering recur across different signed-network mining tasks.The survey cites node ranking, community detection, recommendation, and link prediction as examples of cross-task technique reuse.
- Technique Perspective: Spectral clustering supports community detection through graph partitioning and also generates node vector representations for other tasks.Its partition objective minimizes the cut between disjoint node sets.