{"id":182639,"date":"2008-03-17T00:00:00","date_gmt":"2009-10-31T09:50:45","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/candidate-talk-dynamics-of-real-networks-patterns-and-algorithms\/"},"modified":"2016-09-09T09:57:44","modified_gmt":"2016-09-09T16:57:44","slug":"candidate-talk-dynamics-of-real-networks-patterns-and-algorithms","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/candidate-talk-dynamics-of-real-networks-patterns-and-algorithms\/","title":{"rendered":"Candidate Talk: Dynamics of real networks: patterns and algorithms"},"content":{"rendered":"<div class=\"asset-content\">\n<p>With the advent of the Web, large scale social and<br \/>\ninformation networks containing detailed traces of human activity have<br \/>\nbecome available. This offers great opportunities to measure, model and<br \/>\npredict actions of millions of people. For example, we had an<br \/>\nopportunity to analyze a \u201cplanetary scale\u201d Microsoft Instant<br \/>\nMessenger network that contains 240 million people, with more than 1<br \/>\nbillion conversations per day (4.5TB of data), which makes it the<br \/>\nlargest social network analyzed to date.<\/p>\n<p>In this talk I will focus on two aspects of the dynamics of large real-<br \/>\nworld networks: (a) dynamics of information diffusion and cascading<br \/>\nbehavior in networks, and (b) dynamics of time evolving networks.<br \/>\nFirst, I will consider network cascades that are created by the<br \/>\ndiffusion process where behavior spreads from node to node like an<br \/>\nepidemic. We study two related scenarios: information diffusion among<br \/>\nblogs, and a viral marketing setting of 16 million product<br \/>\nrecommendations among four million people. Motivated by our empirical<br \/>\nobservations we develop algorithms for finding influential bloggers and<br \/>\ndetecting disease outbreaks. We exploit the \u201dsubmodularity\u201d principle<br \/>\nto develop an efficient algorithm that achieves near optimal solutions,<br \/>\nwhile scaling to large problems and being 700 times faster than a<br \/>\nsimple greedy algorithm. Second, in our recent work we found<br \/>\ninteresting and counter intuitive patterns, which change some of the<br \/>\nbasic assumptions about fundamental structural properties of networks<br \/>\nvarying over time. Leveraging our observations we developed a Kronecker<br \/>\ngraph generator model that explains processes governing network<br \/>\nevolution. Moreover, we can fit the model to large networks, and then<br \/>\nuse it to generate realistic graphs and give formal statements about<br \/>\ntheir properties. Estimating the model naively takes O(N!N<sup>2<\/sup>) while we<br \/>\ndevelop a linear time O(E) algorithm.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 \u201cplanetary scale\u201d Microsoft Instant Messenger network that contains 240 million people, [&hellip;]<\/p>\n","protected":false},"featured_media":194716,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-182639","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/s8tiODm5Bzc","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/182639"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/182639\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/194716"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=182639"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=182639"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=182639"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=182639"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=182639"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=182639"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=182639"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}