1、Advanced Topics in Data Mining Special focus: Social Networks,Reminders,By the end of this week/ beginning of next we need to have a tentative presentation scheduleEach one of you should send me an email about a theme by Friday, February 22.,What did we learn in the last lecture?,What did we learn i
2、n the last lecture?,Degree distribution What are the observed degree distributions Clustering coefficient What are the observed clustering coefficients? Average path length What are the observed average path lengths?,What are we going to learn in this lecture?,How to generate graphs that have the de
3、sired properties Degree distribution Clustering coefficient Average path lengthWe are going to talk about generative models,What is a network model?,Informally, a network model is a process (radomized or deterministic) for generating a graph Models of static graphs input: a set of parameters , and t
4、he size of the graph n output: a graph G(,n) Models of evolving graphs input: a set of parameters , and an initial graph G0 output: a graph Gt for each time t,Families of random graphs,A deterministic model D defines a single graph for each value of n (or t)A randomized model R defines a probability
5、 space Gn,P where Gn is the set of all graphs of size n, and P a probability distribution over the set Gn (similarly for t) we call this a family of random graphs R, or a random graph R,Erds-Renyi Random graphs,Paul Erds (1913-1996),Erds-Renyi Random Graphs,The Gn,p model input: the number of vertic
6、es n, and a parameter p, 0 p 1 process: for each pair (i,j), generate the edge (i,j) independently with probability pRelated, but not identical: The Gn,m model process: select m edges uniformly at random,Graph properties,A property P holds almost surely (or for almost every graph), ifEvolution of th
7、e graph: which properties hold as the probability p increases?Threshold phenomena: Many properties appear suddenly. That is, there exist a probability pc such that for ppc the property holds a.s.What do you expect to be a threshold phenomenon in random graphs?,The giant component,Let z=np be the ave
8、rage degree If z 1, then almost surely, the largest component has size (n). The second largest component has size O(ln n) if z =(ln n), then the graph is almost surely connected.,The phase transition,When z=1, there is a phase transition The largest component is O(n2/3) The sizes of the components f
9、ollow a power-law distribution.,Random graphs degree distributions,The degree distribution follows a binomialAssuming z=np is fixed, as n, B(n,k,p) is approximated by a Poisson distributionHighly concentrated around the mean, with a tail that drops exponentially,Random graphs and real life,A beautif
10、ul and elegant theory studied exhaustivelyRandom graphs had been used as idealized network modelsUnfortunately, they dont capture reality,A random graph example,Departing from the Random Graph model,We need models that better capture the characteristics of real graphs degree sequences clustering coe
11、fficient short paths,Graphs with given degree sequences,input: the degree sequence d1,d2,dnCan you generate a graph with nodes that have degrees d1,d2,dn ? ,Graphs with given degree sequences,The configuration model input: the degree sequence d1,d2,dn process: Create di copies of node i Take a rando
12、m matching (pairing) of the copies self-loops and multiple edges are allowedUniform distribution over the graphs with the given degree sequence,Example,Suppose that the degree sequence isCreate multiple copies of the nodesPair the nodes uniformly at random Generate the resulting network,4,1,3,2,Grap
13、hs with given degree sequences,How about simple graphs ? No self loops No multiple edges,Graphs with given degree sequences,Realizability of degree sequences Lemma: A degree sequence d = d(1),d(n) with d(1)d(2) d(n) and d(1)+d(2)+d(n) even is realizable if and only if for every 1k n-1 it holds that,
14、Graphs with given degree sequences - algorithm,Input : d= d(1),d(n) Output: No or simple graph G=(V,E) with degree sequence d If i=1n d(i) is odd return “No” While 1 do If there exist i with d(i) 0 S(v) = set of nodes with the d(v) highest d values d(v) = 0 For each node w in S(v) E = Eunion (v,w) d
15、(w) = d(w)-1,How can we generate data with power-law degree distributions?,Preferential Attachment in Networks,First considered by Price 65 as a model for citation networks each new paper is generated with m citations (mean) new papers cite previous papers with probability proportional to their inde
16、gree (citations) what about papers without any citations? each paper is considered to have a “default” citation probability of citing a paper with degree k, proportional to k+1Power law with exponent = 2+1/m,Barabasi-Albert model,The BA model (undirected graph) input: some initial subgraph G0, and m
17、 the number of edges per new node the process: nodes arrive one at the time each node connects to m other nodes selecting them with probability proportional to their degree if d1,dt is the degree sequence at time t, the node t+1 links to node i with probabilityResults in power-law with exponent = 3,
18、Variations of the BA model,Many variations have been considered,Copying model,Input: the out-degree d (constant) of each node a parameter The process: Nodes arrive one at the time A new node selects uniformly one of the existing nodes as a prototype The new node creates d outgoing links. For the ith
19、 link with probability it copies the i-th link of the prototype node with probability 1- it selects the target of the link uniformly at random,An example,Copying model properties,Power law degree distribution with exponent = (2-)/(1- ) Number of bipartite cliques of size i x d is ne-iThe model has a
20、lso found applications in biological networks copying mechanism in gene mutations,Small world Phenomena,So far we focused on obtaining graphs with power-law distributions on the degrees. What about other properties? Clustering coefficient: real-life networks tend to have high clustering coefficient
21、Short paths: real-life networks are “small worlds” this property is easy to generate Can we combine these two properties?,Small-world Graphs,According to Watts W99 Large networks (n 1) Sparse connectivity (avg degree z n) No central node (kmax n) Large clustering coefficient (larger than in random g
22、raphs of same size) Short average paths (log n, close to those of random graphs of the same size),Mixing order with randomness,Inspired by the work of Solmonoff and Rapoport nodes that share neighbors should have higher probability to be connected Generate an edge between i and j with probability pr
23、oportional to RijWhen = 0, edges are determined by common neighbors When = edges are independent of common neighbors For intermediate values we obtain a combination of order and randomness,mij = number of commonneighbors of i and j,p = very small probability,Algorithm,Start with a ring For i = 1 n S
24、elect a vertex j with probability proportional to Rij and generate an edge (i,j) Repeat until z edges are added to each vertex,Clustering coefficient Avg path length,small world graphs,Watts and Strogatz model WS98,Start with a ring, where every node is connected to the next z nodes With probability
25、 p, rewire every edge (or, add a shortcut) to a uniformly chosen destination. Granovetter, “The strength of weak ties”,order,randomness,p = 0,p = 1,0 p 1,Watts and Strogatz model WS98,Start with a ring, where every node is connected to the next z nodes With probability p, rewire every edge (or, add
26、a shortcut) to a uniformly chosen destination. Granovetter, “The strength of weak ties”,order,randomness,p = 0,p = 1,0 p 1,Clustering Coefficient Characteristic Path Length,log-scale in p,When p = 0, C = 3(k-2)/4(k-1) L = n/k,For small p, C L logn,Next Class,Some more generative models for social-network graphs,
