Transcript Slide

IEEE Intelligent Systems, Special Issue on Social Learning, 2010
1
Goal: analyzing how the networks evolve
over time
• Models of social networks
– networks follow power-law degree distribution,
– have a small diameter
– exhibit small-world structure and community structure
• Social networks is a function of time
– The Obama network
• Various Models have been studied
– many tools have been built (example)
2
Dynamic Models
• The preferential attachment model:
– assumes that new network nodes have a
higher probability of forming links with highdegree nodes
– creating a “rich-get-richer” effect
Network diameter
shrinks over time
From: Leskovec et al. KDD’05
3
Questions raised in this paper
• Studying network formation strategies
– Microscopic level
• Graph Evolution Rules
– Association rules
– From current network configurations
• Predict future edges and nodes
• Rules
– Old-old
– Old-new
– New-new
4
Co-authorship Network
• http://www.arnetminer.org/viewperson.do?i
d=486660&name=Qiang%20Yang
• http://academic.research.microsoft.com/Vi
sualExplorer#435931
5
Basic Concepts: Frequent Patterns
and Association Rules (from J. Han)
Transaction-id
Items bought
10
A, B, C
20
A, C
30
A, D
40
B, E, F
Customer
buys both
Customer
buys beer
Customer
buys diaper
• Itemset X={x1, …, xk}
• Find all the rules XY with min
confidence and support
– support, s, probability Pr(X,Y)
– confidence, c, conditional
probability Pr(Y|X).
Let min_support = 50%,
min_conf = 50%:
A  C (50%, 66.7%)
C  A (50%, 100%)
6
Association Rules on Graphs
• First, we need to record
time stamps on graphs
– Nodes
– Edges
• A large-degree node (label 3),
which at time t is connected to
four medium-degree nodes
(label 2), at time t +1 will be
connected to a fifth node.
– The collaboration-rich
researcher gets richer.
7
G-span based GER Algorithm
8
Example GER Rules
9
Too many rules? Ranking
10
Datasets
11
Precision-Recall Curve
12
Dataset Statistics
13
14
15