ASONAM'09 Day 1 Keynote

Dr. Faloutsos (CMU) did a good job of kicking off the discussion with real-world examples of applicability of graph analysis (food web to determine most important animals in ecosystem, boards of directors to find conflicts of interest, ...). He showed experimental properties extracted from Zipf (log/log) plots of degree vs. rank applied to web links, click-stream data, citeseer and trust data (epinions.com). The slope of these graphs tend to 1.7 and the eigenvalue slope is ~0.8. This, he said, could be very good to identify outliers in connectivity: he applied it to call records to find telemarketers.

His research group has explored how graphs grow over time. They found that the diameter of dynamic graphs shrink (i.e., the graph becomes increasingly more connected). For Autonomous Systems (ASes), the number of nodes increased by 2 in 18 months while the number of edges increased with a slope ~1.7 (more than double); he noted that a slope of 1 indicates a tree (hierarchy) while a slope of 2 is a clique. They explored the non-largest connected component (NLCC) to determine whether is grows, shrinks, or stabilizes over time. And they found...that is oscillates between the 3 states. They observed edge inter-arrival time in LinkedIn data and found that popularity declines in a power-law distribution with slope -1.6 (close to Barabasi -1.5) -- that is, the "rich get richer".

Finally, he has been researching graph generation for 2 reasons:

1. as a data source when privacy concerns arise
2. to understand and enumerate valuable properties of dynamic graphs

They were able to generate pseudo-network graphs that had the properties one expects of the graphs -- and they can be perpetuate as the graph grows using their techniques. Their work can be found in ICMD'08 and KDD'07. He put in a plug for Hadoop MapReduce for graph processing.