Component Properties Each sepnenent ie vouch 问题: 在这样一个巨大的图(200 M nodes,1.5 G edges) 上, Diameter怎么计算出来的? er Diameter, maximal minimal path length (? Maximal and average diameter is infinite 28 for SCC 500 for entire graph Average length 16 directed path exists),7(undirected) Shortest directed path between 2 nodes in SCC: 16-20 links on average
Component Properties ◼ Each component is roughly same size ◼ ~50 million nodes ◼ Probability of a path between any 2 nodes ~1 quarter (0.24) ◼ Diameter, maximal minimal path length(?) ◼ Maximal and average diameter is infinite ◼ 28 for SCC, 500 for entire graph ◼ Average length ◼ 16 (directed path exists), 7 (undirected) ◼ Shortest directed path between 2 nodes in SCC: 16-20 links on average 问题： 在这样一个巨大的图(200M nodes, 1.5G edges) 上，Diameter怎么计算出来的？
Nc&IS Web上节点的分布如何?
Web上节点的分布如何？
站点入度分布 会是下面哪一种情况? Number of Number of websites websites Number of links-in Number of links. to a website to a website Normal distribution: A small number Power law distribution: A very large of sites have few or no links a large number of sites have few or no links number of sites have a moderate a small number have a moderate number of links into them and a number of links into them, a tiny small number have a large number number have a very large number of of links pointing to them links pointing to them
站点入度分布 ◼ 会是下面哪一种情况？
80/20原则 Pareto principle for many phenomena, 80% of the consequences stem from 20% of the causes (Vilfredo Pareto) scale free Head Long tail ong Products
80/20 原则 ◼ Pareto principle : for many phenomena, 80% of the consequences stem from 20% of the causes. (Vilfredo Pareto) scale free Long tail
Power law ±0 35 ower-law scaling: p(k)=k"or logp(k)]=-Alog(k) 30 20 15 exponential scaling: p(k)=e" or loglp(k)]=-7k 10 2 number of connections, k
Power law