A Label Propagation-Based Algorithm for Community Discovery in Online Social Networks

LIVB Algorithm: Enhancing Community Discovery via Label Influence Vectors

A Label Propagation-Based Algorithm for Community Discovery in Online Social Networks

2013-01-01

Yitong Wang, Yurong Zhao, Zhuoxiang Zhao, Zhicheng Liao

Summary

Problem

Method

Results

Takeaways

Abstract

The paper introduces LIVB (Label Influence Vector Based), a community discovery algorithm for online social networks. It leverages a novel label propagation mechanism that distinguishes between static and dynamic node influences to identify higher-quality, topic-concentrated communities in near-linear time.

TL;DR

Community discovery in massive online social networks (OSNs) often trades off between accuracy and speed. While the Label Propagation Algorithm (LPA) is famously fast (near-linear time), it is notoriously unstable and "blind" to the semantic richness of modern Web 2.0 data. This paper presents LIVB, an improved LPA variant that uses Influence Vectors to prioritize more relevant labels, resulting in communities with significantly higher topic concentration and lower fragmentation.

The Problem: The High Cost of Discovery

As social networks evolved from simple person-to-person links into complex webs of users, posts, videos, and comments, traditional algorithms hit a wall:

Computational Bottlenecks: Methods like Spectral Clustering or Girvan-Newman are too slow for millions of nodes.
Structural Blindness: Standard LPA treats every neighbor equally. In reality, a "friend" link (static) and a "comment" interaction (dynamic) carry different social weights.
Instability: If two labels are equally common among neighbors, LPA flips a coin. This randomness leads to inconsistent community structures across different runs.

Methodology: The Label Influence Vector

The core innovation of LIVB is the transition from a simple "majority vote" to a vector-based influence calculation.

1. Multi-Entity Graph Modeling

Instead of a simple unipartite graph, LIVB models users, stories, and comments as distinct node types. This allows the propagation process to capture the implicit social circles formed when users interact with the same content.

Node Types and Relations

2. Static vs. Dynamic Influence

Every label $l$ in a neighbor's set is evaluated using a vector $(S t a t i c V a l u e, D y nami c V a l u e)$ :

Static Value: Focuses on stable relationships (e.g., friend lists) and the structural importance (degree) of the nodes holding that label.
Dynamic Value: Focuses on interaction intensity (e.g., how many comments or "diggs" were shared).

The label update rule follows a deterministic comparison: $V_{1} > V_{2} ⟺ \frac{S t a ( l _{1} ) - S t a ( l _{2} )}{ma x ( S t a ( l _{1} ) , S t a ( l _{2} ))} + \frac{D y n ( l _{1} ) - D y n ( l _{2} )}{ma x ( D y n ( l _{1} ) , D y n ( l _{2} ))} > 0$

This formula effectively "normalizes" the different scales of static and dynamic interactions, ensuring that a highly active dynamic interest can outweigh a weak static link, and vice versa.

Experiments: Does it Actually Work?

The authors tested LIVB against the original LPA on a real-world dataset from Digg.

Topic Concentration

A key finding was that LIVB creates communities that make more "sense" from a human perspective. In an entire graph trial, LIVB increased the concentration of the top-8 topics by 8.32%. While LPA often created tiny, fragmented clusters, LIVB merged nodes into more uniform and semantically related groups.

Comparison of Communities (Note: Refer to Figures 4 & 5 in the paper for the visual distribution of topic coverage showing LIVB's superior concentration.)

Semantic Overlapping

In a focused experiment on the "food" topic, the authors measured Tag Overlapping. If a community is high quality, the tags used by its members should overlap significantly.

LIVB: Only 2 out of 30 communities had zero overlapping.
LPA: 38 out of 120 communities had zero overlapping.

Tag Overlapping Results

Critical Analysis & Conclusion

The Takeaway

LIVB successfully brings "intelligence" to the Label Propagation Algorithm. By replacing random selection with a structured influence vector, it handles the heterogeneity of modern social media without losing the $O (n + m)$ efficiency that makes LPA attractive.

Limitations & Future Work

While LIVB improves stability, it still relies on iterative propagation, which can occasionally struggle with convergence in specific bipartite structures (though asynchronous updates mitigate this). The authors aim to expand this into overlapping community discovery, acknowledging that in the real world, a user belongs to multiple social circles (e.g., "Foodies" and "Techies") simultaneously.

Ultimately, LIVB proves that for big data social analysis, the "influence" of a node is just as important as the "topology" of the network.

Find Similar Papers

Try Our Examples

Search for recent papers that extend the Label Propagation Algorithm (LPA) using heterogeneous information networks (HIN) for community detection.
Which paper first proposed the modularity metric Q, and what are the known limitations when applying it to multi-type entity social networks?
Explore how Label Influence Vector concepts have been applied to signed graphs or directed graphs in recent social network analysis literature.

Contents

LIVB Algorithm: Enhancing Community Discovery via Label Influence Vectors

1. TL;DR

2. The Problem: The High Cost of Discovery

3. Methodology: The Label Influence Vector

3.1. 1. Multi-Entity Graph Modeling

3.2. 2. Static vs. Dynamic Influence

4. Experiments: Does it Actually Work?

4.1. Topic Concentration

4.2. Semantic Overlapping

5. Critical Analysis & Conclusion

5.1. The Takeaway

5.2. Limitations & Future Work