Challenge: Weighted graph projection and analysis

Solution

Label Propagation detects communities by having nodes adopt the most common label among their neighbors.

The algorithm works iteratively: 1. Each node starts with its own unique label (community ID) 2. In each iteration, nodes adopt the label that appears most frequently among their neighbors 3. This continues until labels stabilize or a maximum iteration count is reached

Labels "propagate" through the network as neighbors influence each other, naturally forming communities of nodes that are densely connected.

Solution

Label Propagation uses local neighbor voting, while Louvain/Leiden optimize modularity globally.

Label Propagation: - Uses a simple voting mechanism: each node adopts the most common label among its neighbors - Makes local decisions based only on immediate connections - Fast and simple, but results can be sensitive to initialization

Louvain/Leiden: - Optimize modularity—a global metric measuring how well-defined communities are - Consider the entire network structure when making decisions - Hierarchical: they aggregate communities into super-nodes and repeat - Generally more stable and produce higher-quality communities

Both detect communities, but through fundamentally different approaches—local voting vs. global optimization.

Solution

You get different community assignments each time.

Label Propagation is non-deterministic—it can produce different results on successive runs. You might notice:

This happens because Label Propagation is sensitive to: 1. Initialization order: Which nodes update their labels first can affect the final outcome 2. Tie-breaking: When a node’s neighbors have equal votes for multiple labels, the algorithm must break ties randomly 3. Update sequence: The order in which nodes process their neighbors' labels

This is normal behavior for Label Propagation and one of its trade-offs for speed and simplicity.

Solution

The algorithm’s reliance on neighbor voting and tie-breaking introduces randomness.

Label Propagation is non-deterministic because:

Tie-breaking: When a node’s neighbors have equal votes for multiple labels (e.g., 3 neighbors in community A, 3 in community B), the algorithm must break the tie. This tie-breaking is random, leading to different outcomes.

Update order: The sequence in which nodes update their labels can affect the final result. If node X updates before node Y, it might influence Y’s decision differently than if Y updated first.

Cascading effects: A single tie-break early in the algorithm can cascade through the network, causing different nodes to join different communities as the labels propagate.

This is a known trade-off: Label Propagation is fast and simple, but less stable than modularity-optimizing algorithms like Louvain or Leiden, which are deterministic (same input = same output).

Solution

Weights make stronger connections more influential in the neighbor voting process.

In weighted Label Propagation:

Unweighted behavior: Each neighbor gets one "vote" for its community label, regardless of connection strength.

Weighted behavior: Each neighbor’s vote is weighted by the relationship property. A neighbor connected by a high-weight relationship (imdbRating: 9.2) has more influence than a neighbor connected by a low-weight relationship (imdbRating: 4.1).

In your actor-movie network: - Actors and movies connected through highly-rated films have stronger influence on each other’s community assignment - Communities tend to form around quality collaborations rather than just any collaboration - This produces more meaningful clusters based on film success, not just co-appearance

Weights essentially amplify or diminish each neighbor’s influence in the voting process, allowing the algorithm to prioritize important connections over weak ones.