Semi-Supervised Community Detection Using Structure and Size

Arjun Bakshi, Srinivasan Parthasarathy, and Kannan Srinivasan

​

Presented at: IEEE International Conference on Data Mining

November 17-20, 2018 in Singapore

​

Community Detection

• What if some communities are known?

Semi-Supervised Community Detection

• If some communities in the graph are known, then can we detect others like them?
• What do we mean by “like them”?
• Same size distribution as known communities
• Similar patterns in structure or composition as known communities

​

Size Information

• Sizes of communities depends on dataset
• Detected communities too large → low precision
• Detected communities too small → low recall

Data source: http://snap.stanford.edu/data/

Structure in Communities

• Nodes → Roles
• Core,
• Peripheral
• Bridge
• Homophilic, etc.

​

• Community → Collection of nodes with certain roles
• Nodes with same labels
• Specific distribution of labels

Defining Structure of a Community

• Given:
• G, labeled graph
• C, a community within it
• Goal:
• A feature vector for community’s structure/composition

Patterns in Communities vs Random Subgraphs

• Compare random subgraphs vs communities in the defined feature space

​

• DBLP dataset

Semi-Supervised Community Detection

• If some communities in the graph are known, then can we detect others like them?

​

• What do we mean by “like them”?
• Same size distribution as known communities
• Similar patterns in structure or composition as known communities

​

​

• How do we detect them in a large graph?
• Motif matching: Computationally expensive
• Heuristic based:
• Summarize patterns in communities
• Find a node neighborhood with similar patterns
• Expand from that node

Summarizing Community Patterns

DBLP Communities

Identifying Good Seed Nodes

• For a community pattern CP_i and a node n:
• Generate feature vector for ego net of n, FV_n
• Update FV_n based on FVs of n’s neighbors
• Score(CP_i, n) = Similarity of CP_i and FV_n

​

• If Score(CP_i, n) is high, then n is a good seed for generating a community with a pattern CP_i

Image source: RolX/Discovering Roles and Anomalies in Graphs: Theory and Applications, Eliassi-Rad et al. ECML PKDD 2013

Communities

Node ego nets

✅

✅

Putting it together: The Bespoke Algorithm

Putting it together: The Bespoke Algorithm

• Community detection:
• Pick CP_i based on frequency in the training dataset
• Pick a node, n, with a high Score(CP_i, n)
• Pick a target community size, T, from size distribution associated with CP_i
• Expand in Breadth First manner till T nodes are reached

CP₁

CP₄

Size of communities in CP₁

Size of communities in CP₄

Size of communities in CP₃

Size of communities in CP₂

CP₂

CP₃

Results: Datasets

• SNAP Stanford data repository ¹

• Bespoke trains on <100 communities in all cases

1: http://snap.stanford.edu/data/

Results: F1 scores

• Better than meta-data (CESNA), embedding (ComE), and supervised (BigClam-Assisted) methods

Results: F1 Scores

• Importance of Size and Structure information

Results: Community Patterns (Amazon)

Conclusion

• Present a feature space for exploring patterns in communities
• Uses quick node labeling method for unlabeled graphs
• Show significantly divergent patterns in communities vs random subgraphs
• Proposed algorithm achieves higher F1 scores, lower run times

​