A Framework for Finding Communities in Dynamic Social Networks一种动态的社会网络社区发现框架 共24页

发布于:2021-08-02 20:03:34

A Framework for Finding Communities in Dynamic Social
Networks
Chayant Tantipathananandh, Tanya Berger-Wolf University of Illinois at Chicago David Kempe University of Southern California

Social Networks

History of Interactions

1

Macintosh PICT

2

3

im age form at

is not supported

Macintosh PICT

Macintosh PICT im age form at

im age form at is not supported

is not supported

t=1

5
Macintosh PICT im age form at is not supported

4
Macintosh PICT im age form at is not supported

Assume discrete time and interactions in form of complete subgraphs.

1 Aggregated

network

2

1

3
3

2

2

5

1

1

4

History of interactions 5 4 2 3 1 t=1

5 2 3 4 1 t=2

52

4 1 t=3

5 23 4

t=4

5 2 4 3 1 t=5

Community Identification
What is community?
“Cohesive subgroups are subsets of actors among whom there are relatively strong, direct, intense, frequent, or positive ties.” [Wasserman & Faust ‘97]
Notions of communities: Static
? Centrality and betweenness [Girvan & Newman ‘01] ? Correlation clustering [Basal et al. ‘02] ? Overlapping cliques [Palla et al. ’05]
Dynamic
? Metagroups [Berger-Wolf & Saia ’06]

The Question: What is dynamic community?

t=1 5 4 2 3 1

t=2 5 2 3 4 1

t=3 5 2

41

t=4 5 2 3 4

t=5 5 2 4 3 1
? A dynamic community is a subset of individuals
that stick together over time.
? NOTE: Communities ≠ Groups

Approach: Graph Model

t=1 5 4 2 3 1

t=2 5 2 3 4 1

t=3 5 2

41

t=4 5 2 3 4

t=5 5 2 4 3 1

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

Approach: Assumptions
Required
? Individuals and groups represent exactly one community at a
time.
? Concurrent groups represent distinct communities.
Desired
?Conservatism: community affiliation changes are rare. ?Group Loyalty: individuals observed in a group belong
to the same community.
?Parsimony: few affiliations overall for each individual.

Approach: Color = Community
Valid coloring: distinct color of groups in each time step

Approach: Assumptions
Required
? Individuals and groups represent exactly one community at a
time.
? Concurrent groups represent distinct communities.
Desired
?Conservatism: community affiliation changes are rare. ?Group Loyalty: individuals observed in a group belong
to the same community.
?Parsimony: few affiliations overall for each individual.

Costs
?Conservatism: switching cost (α) ?Group loyalty:
-Being absent (β1) -Being different (β2) ?Parsimony: number of colors (γ)

Approach: Assumptions
Required
? Individuals and groups represent exactly one community at a
time.
? Concurrent groups represent distinct communities.
Desired
?Conservatism: community affiliation changes are rare. ?Group Loyalty: individuals observed in a group belong
to the same community.
?Parsimony: few affiliations overall for each individual.

Costs
?Conservatism: switching cost (α) ?Group loyalty:
-Being absent (β1) -Being different (β2) ?Parsimony: number of colors (γ)

Approach: Assumptions
Required
? Individuals and groups represent exactly one community at a
time.
? Concurrent groups represent distinct communities.
Desired
?Conservatism: community affiliation changes are rare. ?Group Loyalty: individuals observed in a group belong
o the same community.
?Parsimony: few affiliations overall for each individual.

Costs
?Conservatism: switching cost (α) ?Group loyalty:
-Being absent (β1) -Being different (β2) ?Parsimony: number of colors (γ)

Problem Definition
? Minimum Community Interpretation
For a given cost setting, (α,β1,β2,γ), find vertex coloring that minimizes total cost.
? Color of group vertices = Community structure ? Color of individual vertices = Affiliation sequences
? Problem is NP-Complete and APX-Hard

Model Validation and Algorithms
? Model validation: exhaustive search for an exact minimum-cost
coloring.
? Heuristic algorithms evaluation: compare heuristic results to OPT. ? Validation on data sets with known communities from simulation
and social research
- Southern Women data set (benchmark)

Southern Women Data
Set
by Davis, Gardner, and Gardner, 1941

Photograph by Ben Shaln, Natchez, MS, October; 1935

Aggregated network

Event participation

Ethnography
by Davis, Gardner, and Gardner, 1941

Core (1-4) Periphery (5-7)

Periphery (11-12) Core (13-15)

An Optimal Coloring: (α,β1,β2,γ)=(1,1,3,1)

Periphery

Core

Core

Periphery

An Optimal Coloring: (α,β1,β2,γ)=(1,1,1,1)

Core

Core

Periphery

Conclusions
? An optimization-based framework for finding communities in
dynamic social networks.
? Finding an optimal solution is NP-Complete and APX-Hard. ? Model evaluation by exhaustive search. ? Heuristic algorithms for larger data sets. Heuristic results
comparable to optimal.

Thank You
Poster #6 this evening

Dan Rubenstein Princeton
Ilya Fischoff Siva Sundaresan

Computational Population Biology Lab UIC

compbio.cs.uic.edu

David Kempe USC

Tanya Berger-Wolf
Poster#6 this evening

Jared Saia UNM

Simon Levin Princeton

Habiba

Chayant

Mayank Lahiri

Tantipathananandh

Muthu Google

更多精品资源请访问
docin/sanshengshiyuan doc88/sanshenglu


相关推荐

最新更新

猜你喜欢