Dynamics of real networks: patterns and algorithms

98 views · Published 6 September 2016 · 1:19:31 · Indexed 18 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

With the advent of the Web, large scale social and  information networks containing detailed traces of human activity have  become available. This offers great opportunities to measure, model and  predict actions of millions of people. For example, we had an  opportunity to analyze a ``planetary scale'' Microsoft Instant  Messenger network that contains 240 million people, with more than 1  billion conversations per day (4.5TB of data), which makes it the  largest social network analyzed to date.    In this talk I will focus on two aspects of the dynamics of large real-  world networks: (a) dynamics of information diffusion and cascading  behavior in networks, and (b) dynamics of time evolving networks.  First, I will consider network cascades that are created by the  diffusion process where behavior spreads from node to node like an  epidemic. We study two related scenarios: information diffusion among  blogs, and a viral marketing setting of 16 million product  recommendations among four million people. Motivated by our empirical  observations we develop algorithms for finding influential bloggers and  detecting disease outbreaks. We exploit the ''submodularity'' principle  to develop an efficient algorithm that achieves near optimal solutions,  while scaling to large problems and being 700 times faster than a  simple greedy algorithm. Second, in our recent work we found  interesting and counter intuitive patterns, which change some of the  basic assumptions about fundamental structural properties of networks  varying over time. Leveraging our observations we developed a Kronecker  graph generator model that explains processes governing network  evolution. Moreover, we can fit the model to large networks, and then  use it to generate realistic graphs and give formal statements about  their properties. Estimating the model naively takes O(N!N^2) while we  develop a linear time O(E) algorithm.

More from this channel