Basic Models

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다.

 

We have now seen that densification power laws and shrinking effective diameters are properties that hold across a range of diverse networks.

 

"How do we build models of network generations of evolution?"

 

Lattice Networks

Lattice networks have High clustering coefficients, Large diameter

 

Small-world  Models

• Small-world Model have High clustering Low diameter, Huge giant connected component.
• Does not lead to the correct degree distribution, no heavy-tail

1. Start with a low-dimensional regular lattice
   Has high clustering coefficient
2. Rewire: introduce randomness for 'shortcuts'
   For each edge with prob. p move the other end to a random node

 

Preferential Attachment

• Repeats adding a new node, create \(m\) out-links
• Probability of linking a node \(i\) is proportional to its degree \(d_i\)

$$ P = {d_i \over \sum d_j}  $$

• Richer gets richer model(high degree일수록 새로운 node가 붙을 확률 증가)
• Leads to power-law in-degree distributions
• But all nodes have equal out-degree, does not have communities

$$ P(k) \propto k^{-3} $$

 

 

Edge Copying Model

• Power-law degree distributions
• Generates communities
• But, the diameter does not shrink

1. Add a node and choose \(k\) the number of edges to add
2. With prob \(\beta\) select \(k\) random vertices and link to them
3. With prob \(1-\beta\), \(k\) edges are copied from a randomly chosen node