Mining Graphs and Tensors

Graphs - why should we care?

1. network of companies & board-of-directors members
2. 'viral'marketing
3. web-log(‘blog’) news propagation
4. computer network security: email/IP traffic and anomaly detection

?

Problem#1:How do real graphs look like?

Degree distributions

Power law in the degree distribution

?

Eigenvalues

Power law in the eigenvalues of the adjacency matrix

?

Triangles

Real social networks have a lot of triangles,eg Friends of friends are friends

X-axis: #of Triangles a node participates in?? Y-axis:count of such nodes

But triangles are expensive to compute,Can we do that quickly?

#triangles= 1/6 Sum (λi)(and,because of skewness,we only need the top few eigenvalues!)

?

Weights

How do the weights of nodes relate to degree?

Snapshot Power Law: At any time,total incoming weight of a node is proportional to in-degree with PL exponent 'iw':? i.e. 1.01 < iw <1.26,super-linear

?

?

Problem#2:How do they evolve?

?

Diameter

Diameter?shrinks over time

?

Temporal Evolution of the Graphs

?

N(t) … nodes at time t??? E(t) … edges at time t

Suppose that? N(t+1) = 2 * N(t)??

Q: what is your guess for?? E(t+1) =? 2 * E(t)

A: over-doubled!? But obeying the Densification Power Law

?

GCC and NLCC

Q1: How does the GCC emerge?

Most real graphs display a gelling point.

After gelling point,they exhibit typical behavior.?This is marked by a spike in diameter.

?

Q2: How do NLCC emerge and join with the GCC?

(NLCC= non-largest conn. components)

Do they continue to grow in size? or do they shrink? or stabilize?

After the gelling point,the GCC takes off,but NLCC's remain ~constant (actually,oscillate).

?

?

Blogs,linking times,cascades

Q1:popularity-decay of a post?

Post popularity drops-off – POWER LAW!

Exponent?-1.6 (close to -1.5: Barabasi's stack model)

?

Q2:degree distributions?

44,356nodes,122,153 edges.? Half of blogsbelong to largest connected component.

?

?

?References：

Mining Graphs and Tensors------Christos ?Faloutsos CMU