Source-linked AI summary
Signed Networks in Social Media
Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg
TL;DR
Online social-network research has largely overlooked how positive and negative relationships jointly shape network structure, despite their coexistence in social media. The paper adapts balance and status theories to three signed online networks and finds that balance fits undirected patterns, while status better explains directed, evolving links. These results provide a large-scale evaluation of signed-network theories and a framework for interpreting social-media linking behavior.
Problem
Online-network research has focused mostly on positive links, leaving the interplay of positive and negative relationships and its structural implications comparatively unexplored.
Method
The paper adapts structural balance and status theories to signed networks from Epinions, Slashdot, and Wikipedia, comparing their predictions across directed and undirected representations.
Results
Balance is consistent with undirected patterns, whereas status more effectively explains directed links in evolving networks across the three datasets.
Takeaways & Limitations
Different theories can be appropriate to different representations of the same network, with status capturing directed social-media relations that encode relative standing.
Takeaways & Limitations
The current status theory does not fully account for a behavioral asymmetry in cases where A is predicted to impute low status to both herself and B.
Abstract
from arXiv · showhide
Relations between users on social media sites often reflect a mixture of positive (friendly) and negative (antagonistic) interactions. In contrast to the bulk of research on social networks that has focused almost exclusively on positive interpretations of links between people, we study how the interplay between positive and negative relationships affects the structure of on-line social networks. We connect our analyses to theories of signed networks from social psychology. We find that the classical theory of structural balance tends to capture certain common patterns of interaction, but that it is also at odds with some of the fundamental phenomena we observe --- particularly related to the evolving, directed nature of these on-line networks. We then develop an alternate theory of status that better explains the observed edge signs and provides insights into the underlying social mechanisms. Our work provides one of the first large-scale evaluations of theories of signed networks using on-line datasets, as well as providing a perspective for reasoning about social media sites.
INTRODUCTION
The paper studies positive and negative links in online social networks by adapting signed-network theories from social psychology. It finds that balance fits undirected patterns, whereas status better explains directed, evolving links and suggests how different applications use linking mechanisms.
- Motivation: Online network analysis must bridge rich positive and negative relationships with simplified pairwise representations.The paper frames this as a fundamental research problem and focuses on signed links in social media.
- Approach: The study adapts signed-network theories to analyze three applications and infer how positive and negative links are used.It evaluates trust or distrust on Epinions, friends or foes on Slashdot, and votes for Wikipedia administrators.
- Findings: Status theory better explains directed, evolving networks by interpreting positive links as higher-status judgments and negative links as lower-status judgments.Status propagates relative levels along signed paths and can produce predictions opposite to balance theory.
- Findings: Structural balance aligns with undirected data: two-positive-edge triangles are massively underrepresented, while three-positive-edge triangles are massively overrepresented.This alignment appears when link directions are disregarded, although three-negative triangles are also overrepresented in two datasets.
- Implications: The findings indicate that balance and status can be appropriate at different representational levels of the same network.Balance is more consistent with undirected representations, while status is more consistent with directed ones.
- Further implications: Reciprocated links show stronger balance patterns but constitute only a small proportion of links, while positive links are more likely between endpoints sharing multiple neighbors.These structural properties help frame further investigation of individual variation in linking behavior.
RELATED WORK
Prior online-network research largely treated links as positive or pursued negative relationships for other goals. This paper differs by evaluating signed-network theories across online datasets, while distinguishing its status formulation from related social-science uses.
- Online signed-network research: Most online social-network research treated links as implicitly positive, with only limited work explicitly incorporating signs.Prior signed-network studies included vote prediction and global network-property analysis but did not evaluate theories of balance.
- Adjacent research: Other research on negative online relationships focused on behavioral norms or sentiment analysis rather than signed network structure.These approaches addressed deviant behavior or textual attitudes without the paper’s network-theoretic focus.
- Related datasets: The same datasets had been studied for trust, rating mechanisms, and election outcomes, rather than for the organization of signed social networks.The paper therefore reuses established online datasets for a different analytical purpose.
- Conceptual distinction: The paper’s formulation of status as a counterpart to balance is distinct from status concepts used in other social-science traditions.The distinction concerns how status is defined for directed signed networks.
DATASET DESCRIPTION
The study uses three large online networks whose links have explicit positive or negative signs. Each network is inherently directed because the user creating every link is known, and roughly 80% of edges are positive.
- Datasets: The datasets are Epinions trust or distrust links, Slashdot friend or foe links, and Wikipedia positive or negative votes for administrator candidates.Epinions and Slashdot present these relations as social-network features, whereas Wikipedia’s network interpretation is implicit.
- Scale and sign distribution: The networks contain tens to hundreds of thousands of nodes and fewer than one million edges.Their background positive-edge proportions are approximately similar across datasets.
- Scale and sign distribution: Each network is inherently directed because the user who created each edge is identified.This directionality supports analyses that distinguish balance from status interpretations.
- Scale and sign distribution: Roughly 80% of edges have a positive sign in all three networks.The common background sign distribution provides a basis for comparing observed signed patterns with chance expectations.
ANALYSIS OF UNDIRECTED NETWORKS
The undirected analysis compares observed signed-triad frequencies with a random-sign baseline to evaluate structural balance. The data strongly supports Davis’s weak balance pattern, especially the overrepresentation of all-positive triads and underrepresentation of two-positive-edge triads.
- Undirected representation: The analysis represents links as undirected and evaluates structural balance through frequencies of the four possible signed triad types.Triad frequencies are compared with frequencies expected when edge signs are randomly shuffled while preserving their overall distribution.
- Random baseline and surprise: Surprise s(Ti) measures how many standard deviations the observed count of triad type Ti differs from the random-shuffling expectation.Because the datasets contain many triads, even surprise values around 6 are statistically significant, and observed values are typically much larger.
- Observed triad frequencies: The all-positive triad T3 is overrepresented by about 40% in all three datasets, while T2 is underrepresented by about 75% in Epinions and Slashdot and 50% in Wikipedia.These patterns fit the core predictions of structural balance concerning all-positive and two-positive-edge triads.
- Observed triad frequencies: The differing frequencies of T1 and T0 prevent all datasets from satisfying Heider’s stronger theory simultaneously.Davis’s weak balance theory better fits the data because it treats T2 as implausible without favoring either T1 or T0.
ANALYSIS OF EVOLVING DIRECTED NETWORKS
The evolving directed-network analysis incorporates link direction, creation order, and user-specific sign tendencies. These features expose cases where balance theory gives overly simple predictions and motivate a status-based account of directed signed links.
- Directed and evolving networks: Directed analysis treats each link’s sign as generated by its source user and examines triads as links are added over time.A new link closes a triad when its endpoints already connect, directly or indirectly, to a common node.
- Competing predictions: Positive directed cycles are underrepresented, conflicting with balance theory but consistent with status theory.This directional pattern differs from the expectation that positive cycles should be overrepresented under balance.
- Generative and receptive baselines: Users’ overall tendencies to create positive links and to receive positive links define separate generative and receptive baselines.These baselines allow contextualized links to be compared with the sign patterns of their initiators and recipients.
- Competing predictions: Under joint positive endorsement, the closing A-to-B link is more positive than A’s generative baseline but less positive than B’s receptive baseline.This opposite pair of deviations cannot be captured by balance’s simple prediction that A and B should be friends, but status theory is designed to explain it.
Formulating a Theory of Status
The paper formulates status theory by interpreting signed directed links as relative-status judgments and testing contextualized links against initiator and recipient baselines. The framework uses third-party relationships to predict how a closing edge’s sign should deviate from those baselines.
- Motivating example: A motivating example treats positive evaluations as judgments that the recipient has higher status and negative evaluations as judgments that the recipient has lower status.Known evaluations from a third party can support predictions about an unobserved evaluation between two other players.
- Motivating example: When a third player positively evaluates both A and B, A’s evaluation of B should be more positive than A’s random baseline but less positive than B’s received baseline.The two deviations point in opposite directions because the context implies elevated status for both endpoints.
- Contextualized links: A contextualized link, or c-link, is a triple (A, B; X) formed after both A and B already have links to or from X.There are 16 c-link types because each X-to-endpoint relation has four direction-sign possibilities.
- Baseline comparisons: For each c-link type, the analysis compares the observed fraction of positive A-to-B links with initiator generative and recipient receptive baselines.Generative surprise and receptive surprise quantify signed deviations from these respective expectations.
- Status assignment: Status values assign X status 0 and assign A and B status 1 or −1 from the signs and directions of their links with X.Generative or receptive surprise is status-consistent when its sign matches the relevant endpoint’s inferred status.
Results
Across Epinions and Wikipedia, status predictions fit contextualized signed links substantially better than structural balance, while some reciprocation patterns align with balance. The remaining status errors cluster in configurations where both endpoints are assigned low status relative to the intermediary.
- Experimental evaluation: The evaluation uses Epinions and Wikipedia, emphasizing Epinions because its ordered-link dataset is an order of magnitude larger while Wikipedia shows broadly similar results.The theories are compared using consistency with generative and receptive surprise.
- Status versus balance: Status is consistent with generative surprise on 14 c-link types and receptive surprise on 13, including the most abundant joint-endorsement type.On Wikipedia, status is consistent with generative surprise on 12 of 16 triad types and has nearly identical receptive-surprise results to Epinions.
- Status versus balance: Structural balance is consistent with generative surprise for only 8 of 16 c-link types and with receptive surprise for only 7 of 16.Davis’s weaker balance notion produces similar results and remains substantially weaker than status.
- Status-theory exceptions: Status theory’s errors occur almost exclusively when A and B are both assigned low status relative to X, including types t2, t3, t14, and t15.Generative-surprise errors both occur in this group, while two of three receptive-surprise errors do so; these errors form directional-sign duals.
- Status-theory exceptions: The authors conjecture that status theory deviates most strongly when A is predicted to assign low status to both herself and B.They identify refining status theory to account for this asymmetry as a direction for further work.
RECIPROCATION OF DIRECTED EDGES
Reciprocal links are uncommon, but where directed ties become mutual, positive reciprocation strongly follows balance while negative reciprocation mixes balance and status patterns. These alignment rates are similar across Epinions and Wikipedia despite differences in public sign display.
- Only about 3-5% of edges reciprocate an existing link, making mutual back-and-forth interaction a small subset of link creation.
- Balance principles are more pronounced in mutual interactions than in the larger portions of networks where signed links point asymmetrically.
- Positive A-B links are reciprocated positively well over 90% of the time, closely matching balance theory rather than status theory.
- Negative A-B links are reciprocated positively roughly 70% of the time, combining ingredients of both theories and falling below the system-wide 80% positive-link rate.
- Reciprocation patterns are similar in Epinions and Wikipedia despite their different levels of public sign display.
The Role of Triadic Structure in Reciprocation
Reciprocation is shaped not only by the original directed edge but also by the surrounding triad. When the initial triad is balanced, the reciprocal edge is more likely to preserve the original sign.
- A reciprocal B-A edge is significantly more likely to match the original A-B sign when the surrounding A-B-X triad is structurally balanced.
- When the initial triad is unbalanced, reciprocation shows a greater latent tendency to reverse the original sign.
- These findings indicate balance effects in network regions where directed edges point both ways, contrasting with status effects in asymmetric linking.
FURTHER STRUCTURAL ANALYSIS OF SIGNED LINKS
The paper extends its signed-network analysis by examining edge embeddedness and separate positive-only and negative-only subgraphs, treating these structural analyses as undirected graphs.
- The analysis examines edge embeddedness and subgraphs containing exclusively positive or exclusively negative links.
- For these structural results, the networks are analyzed as undirected graphs.
Embeddedness of positive and negative ties
Positive ties cluster within well-embedded groups, whereas negative ties more often bridge those groups. Positive-only networks are more clustered than randomized counterparts, while both sign-specific networks have smaller-than-expected largest components.
- Positive ties are more likely to cluster together, while negative ties tend to act as bridges between islands of positive ties.
- In real data, edges with fewer than around 10 shared neighbors are more negative than expected, while increasing embeddedness predicts increasingly positive edges across all three datasets.
- The embeddedness pattern is most pronounced in Wikipedia, the only site where social relations are explicitly displayed broadly to users.
- All-positive networks have higher clustering than randomized counterparts, whereas all-negative networks have lower clustering.
- Both all-positive and all-negative networks have smaller largest connected components than their randomized counterparts.
- Positive in-degree outliers are more common than expected on Wikipedia, while prolific negative out-degree outliers are less common than expected on Epinions and Slashdot.
CONCLUSION
The paper compares balance and status theories for signed social networks, finding weak structural balance in undirected views but stronger agreement with status theory in directed networks.
- Theoretical framework: The study examines how positive and negative links in social media relate to balance and status theories of signed networks.Balance is a classical social-psychological theory, while status addresses directed signed relationships.
- Empirical patterns: More embedded edges tend to be more positive.
- Theoretical framework: Balance theory predicts that among three people, either all three relationships or only one should be positive.
- Undirected networks: Across all three datasets, triangles with exactly two positive signs are massively underrepresented relative to chance, while triangles with three positive edges are overrepresented.
- Directed networks: In directed networks, many basic predictions of balance theory no longer apply, while directed-link signs closely follow the developed theory of status.Status infers the sign of a link from A to B using their mutual relationships with third parties.