CMS57opomter ci Week 11:Influence Maximization on Social Networks Instructor:Shengyu Zhang
Instructor: Shengyu Zhang 1
Location change for the final 2 classes Nov 17:YIA 404 (Yasumoto International Academic Park康本國祭學術園) ■Nov24:No class. Conference leave. Dec 1:YIA 508 (Yasumoto International Academic Park康本國祭學術園) 2
Location change for the final 2 classes ◼ Nov 17: YIA 404 (Yasumoto International Academic Park 康本國際學術園) ◼ Nov 24: No class. ❑ Conference leave. ◼ Dec 1: YIA 508 (Yasumoto International Academic Park 康本國際學術園) 2
Social network Extensively studied by social scientists for decades. Usually small datasets. Social networks on Internet are gigantic Facebook,Twitter,Linkedln,WeChat,Weibo,.. A large class of tasks/studies are about the influence and information propagation. A typical task:select some seed customers and let them influence others. 3
Social network ◼ Extensively studied by social scientists for decades. ❑ Usually small datasets. ◼ Social networks on Internet are gigantic ❑ Facebook, Twitter, LinkedIn, WeChat, Weibo, … ◼ A large class of tasks/studies are about the influence and information propagation. ◼ A typical task: select some seed customers and let them influence others. 3
Motivating examples Adoption of smart phones. Good:easy access to Internet,many cool apps,etc. Bad:expensive,absorbing too much time,.. ■ Once you start to use smart phones,it's hard to go back. There are not even many choices of traditional phones. Similar adoption:Religion,new idea,virus,.. This lecture focuses on progressive models: once a node becomes active,it stays active. There are also non-progressive models
Motivating examples ◼ Adoption of smart phones. ❑ Good: easy access to Internet, many cool apps, etc. ❑ Bad: expensive, absorbing too much time, … ◼ Once you start to use smart phones, it’s hard to go back. ❑ There are not even many choices of traditional phones. ◼ Similar adoption: Religion, new idea, virus, … ◼ This lecture focuses on progressive models: once a node becomes active, it stays active. ❑ There are also non-progressive models. 4
Popular models Social network:a directed graph G=(V,E). Note that the edges are directed: How much an individual u can influence another individual v is generally different than how much v can influence u.--Just think of stars and fans. We consider the scenario where the diffusion proceeds in discrete time steps. 5
Popular models ◼ Social network: a directed graph 𝐺 = 𝑉,𝐸 . ◼ Note that the edges are directed: ❑ How much an individual 𝑢 can influence another individual 𝑣 is generally different than how much 𝑣 can influence 𝑢. --- Just think of stars and fans. ◼ We consider the scenario where the diffusion proceeds in discrete time steps. 5