第1页 / 共179页
第2页 / 共179页
第3页 / 共179页
第4页 / 共179页
第5页 / 共179页
第6页 / 共179页
第7页 / 共179页
第8页 / 共179页
Information and Influence Propagation in Social Networks.pdf
Acknowledgments
Introduction
Social Networks and Social Influence
Examples of Social Networks
Examples of Information Propagation
Social Influence Examples
Social Influence Analysis Applications
The Flip Side
Outline of This Book
Stochastic Diffusion Models
Main Progressive Models
Independent Cascade Model
Linear Threshold Model
Submodularity and Monotonicity of Influence Spread Function
General Threshold Model and General Cascade Model
Other Related Models
Epidemic Models
Voter Model
Markov Random Field Model
Percolation Theory
Influence Maximization
Complexity of Influence Maximization
Greedy Approach to Influence Maximization
Greedy Algorithm for Influence Maximization
Empirical Evaluation of MC-Greedy(G,k)
Scalable Influence Maximization
Reducing the Number of Influence Spread Evaluations
Speeding Up Influence Computation
Other Scalable Influence Maximization Schemes
Extensions to Diffusion Modeling and Influence Maximization
A Data-Based Approach to Influence Maximization
Competitive Influence Modeling and Maximization
Model Extensions for Competitive Influence Diffusion
Maximization Problems for Competitive Influence Diffusion
Endogenous Competition
A New Frontier – The Host Perspective
Influence, Adoption, and Profit
Influence vs. Adoption
Influence vs. Profit
Other Extensions
Learning Propagation Models
Basic Models
IC Model
Threshold Models
Static Models
Does Influence Remain Static?
Continuous Time Models
Discrete Time Models
Are All Objects Equally Influence Prone?
Algorithms
Experimental Validation
Discussion
Data and Software for Information/Influence: Propagation Research
Types of Datasets
Propagation of Information ``Memes''
Microblogging
Newspapers/blogs/etc.
Propagation of Other Actions
Consumption/Appraisal Platforms
User-Generated Content Sharing/Voting
Community Membership as Action
Cross-Provider Data
Phone Logs
Network-Only Datasets
Citation Networks
Other Networks
Other Off-Line Datasets
Publishing Your Own Datasets
Software Tools
Graph Software Tools
Propagation Software Tools
Visualization
Conclusions
Conclusion and Challenges
Application-Specific Challenges
Prove Value for Advertising/Marketing
Learn to Design for Virality
Correct for Sampling Biases
Contribute to Other Applications
Technical Challenges
Conclusions
Notational Conventions
Bibliography
Authors' Biographies
Index
Series ISSN: 2153-5418
Series ISSN: 2153-5418
Series ISSN: 2153-5418
SYNTHESIS LECTURES ON DATA MANAGEMENT
SYNTHESIS LECTURES ON DATA MANAGEMENT
SYNTHESIS LECTURES ON DATA MANAGEMENT
Series Editor: M. Tamer Özsu, University of Waterloo
Series Editor: M. Tamer Özsu, University of Waterloo
Series Editor: M. Tamer Özsu, University of Waterloo
Information and Influence Propagation in Social Networks
Information and Influence Propagation in Social Networks
Information and Influence Propagation in Social Networks
Wei Chen, Microsoft Reseacrh Asia, Laks V.S. Lakshmanan, University of Bristish Columbia
Wei Chen, Microsoft Reseacrh Asia, Laks V.S. Lakshmanan, University of Bristish Columbia
Wei Chen, Microsoft Reseacrh Asia, Laks V.S. Lakshmanan, University of Bristish Columbia
and Carlos Castillo, Qatar Computing Institute
and Carlos Castillo, Qatar Computing Institute
and Carlos Castillo, Qatar Computing Institute
Research on social networks has exploded over the last decade. To a large extent, this has been fueled by the
Research on social networks has exploded over the last decade. To a large extent, this has been fueled by the
Research on social networks has exploded over the last decade. To a large extent, this has been fueled by the
spectacular growth of social media and online social networking sites, which continue growing at a very fast pace,
spectacular growth of social media and online social networking sites, which continue growing at a very fast pace,
spectacular growth of social media and online social networking sites, which continue growing at a very fast pace,
as well as by the increasing availability of very large social network datasets for purposes of research. A rich body
as well as by the increasing availability of very large social network datasets for purposes of research. A rich body
as well as by the increasing availability of very large social network datasets for purposes of research. A rich body
of this research has been devoted to the analysis of the propagation of information, influence, innovations, infections,
of this research has been devoted to the analysis of the propagation of information, influence, innovations, infections,
of this research has been devoted to the analysis of the propagation of information, influence, innovations, infections,
practices and customs through networks. Can we build models to explain the way these propagations occur? How
practices and customs through networks. Can we build models to explain the way these propagations occur? How
practices and customs through networks. Can we build models to explain the way these propagations occur? How
can we validate our models against any available real datasets consisting of a social network and propagation traces
can we validate our models against any available real datasets consisting of a social network and propagation traces
can we validate our models against any available real datasets consisting of a social network and propagation traces
that occurred in the past? These are just some questions studied by researchers in this area. Information propagation
that occurred in the past? These are just some questions studied by researchers in this area. Information propagation
that occurred in the past? These are just some questions studied by researchers in this area. Information propagation
models find applications in viral marketing, outbreak detection, finding key blog posts to read in order to catch
models find applications in viral marketing, outbreak detection, finding key blog posts to read in order to catch
models find applications in viral marketing, outbreak detection, finding key blog posts to read in order to catch
important stories, finding leaders or trendsetters, information feed ranking, etc. A number of algorithmic problems
important stories, finding leaders or trendsetters, information feed ranking, etc. A number of algorithmic problems
important stories, finding leaders or trendsetters, information feed ranking, etc. A number of algorithmic problems
arising in these applications have been abstracted and studied extensively by researchers under the garb of influence
arising in these applications have been abstracted and studied extensively by researchers under the garb of influence
arising in these applications have been abstracted and studied extensively by researchers under the garb of influence
maximization.
maximization.
maximization.
This book starts with a detailed description of well-established diffusion models, including the independent
This book starts with a detailed description of well-established diffusion models, including the independent
This book starts with a detailed description of well-established diffusion models, including the independent
cascade model and the linear threshold model, that have been successful at explaining propagation phenomena. We
cascade model and the linear threshold model, that have been successful at explaining propagation phenomena. We
cascade model and the linear threshold model, that have been successful at explaining propagation phenomena. We
describe their properties as well as numerous extensions to them, introducing aspects such as competition, budget,
describe their properties as well as numerous extensions to them, introducing aspects such as competition, budget,
describe their properties as well as numerous extensions to them, introducing aspects such as competition, budget,
and time-criticality, among many others. We delve deep into the key problem of influence maximization, which
and time-criticality, among many others. We delve deep into the key problem of influence maximization, which
and time-criticality, among many others. We delve deep into the key problem of influence maximization, which
selects key individuals to activate in order to influence a large fraction of a network. Influence maximization in
selects key individuals to activate in order to influence a large fraction of a network. Influence maximization in
selects key individuals to activate in order to influence a large fraction of a network. Influence maximization in
classic diffusion models including both the independent cascade and the linear threshold models is computationally
classic diffusion models including both the independent cascade and the linear threshold models is computationally
classic diffusion models including both the independent cascade and the linear threshold models is computationally
intractable, more precisely #P-hard, and we describe several approximation algorithms and scalable heuristics that
intractable, more precisely #P-hard, and we describe several approximation algorithms and scalable heuristics that
intractable, more precisely #P-hard, and we describe several approximation algorithms and scalable heuristics that
have been proposed in the literature. Finally, we also deal with key issues that need to be tackled in order to turn
have been proposed in the literature. Finally, we also deal with key issues that need to be tackled in order to turn
have been proposed in the literature. Finally, we also deal with key issues that need to be tackled in order to turn
this research into practice, such as learning the strength with which individuals in a network influence each other,
this research into practice, such as learning the strength with which individuals in a network influence each other,
this research into practice, such as learning the strength with which individuals in a network influence each other,
as well as the practical aspects of this research including the availability of datasets and software tools for facilitating
as well as the practical aspects of this research including the availability of datasets and software tools for facilitating
as well as the practical aspects of this research including the availability of datasets and software tools for facilitating
research. We conclude with a discussion of various research problems that remain open, both from a technical
research. We conclude with a discussion of various research problems that remain open, both from a technical
research. We conclude with a discussion of various research problems that remain open, both from a technical
perspective and from the viewpoint of transferring the results of research into industry strength applications.
perspective and from the viewpoint of transferring the results of research into industry strength applications.
perspective and from the viewpoint of transferring the results of research into industry strength applications.
C
C
C
H
H
H
E
E
E
N
N
N
•
•
•
L
L
L
A
A
A
K
K
K
S
S
S
H
H
H
M
M
M
A
A
A
N
N
N
A
A
A
N
N
N
•
•
•
C
C
C
A
A
A
S
S
S
T
T
T
I
I
I
L
L
L
L
L
L
O
O
O
I
I
I
N
N
N
F
F
F
O
O
O
R
R
R
M
M
M
A
A
A
T
T
T
I
I
I
O
O
O
N
N
N
A
A
A
N
N
N
D
D
D
I
I
I
N
N
N
F
F
F
L
L
L
U
U
U
E
E
E
N
N
N
C
C
C
E
E
E
P
P
P
R
R
R
O
O
O
P
P
P
A
A
A
G
G
G
A
A
A
T
T
T
I
I
I
O
O
O
N
N
N
I
I
I
N
N
N
S
S
S
O
O
O
C
C
C
I
I
I
A
A
A
L
L
L
N
N
N
E
E
E
T
T
T
W
W
W
O
O
O
R
R
R
K
K
K
S
S
S
&
&
&
CM& Morgan Claypool Publishers
CM& Morgan Claypool Publishers
CM& Morgan Claypool Publishers
Information and
Information and
Information and
Influence Propagation
Influence Propagation
Influence Propagation
in Social Networks
in Social Networks
in Social Networks
Wei Chen
Wei Chen
Wei Chen
Laks V.S. Lakshmanan
Laks V.S. Lakshmanan
Laks V.S. Lakshmanan
Carlos Castillo
Carlos Castillo
Carlos Castillo
About SYNTHESIs
About SYNTHESIs
About SYNTHESIs
This volume is a printed version of a work that appears in the Synthesis
This volume is a printed version of a work that appears in the Synthesis
This volume is a printed version of a work that appears in the Synthesis
Digital Library of Engineering and Computer Science. Synthesis Lectures
Digital Library of Engineering and Computer Science. Synthesis Lectures
Digital Library of Engineering and Computer Science. Synthesis Lectures
provide concise, original presentations of important research and development
provide concise, original presentations of important research and development
provide concise, original presentations of important research and development
topics, published quickly, in digital and print formats. For more information
topics, published quickly, in digital and print formats. For more information
topics, published quickly, in digital and print formats. For more information
visit www.morganclaypool.com
visit www.morganclaypool.com
visit www.morganclaypool.com
&
&
&
Morgan Claypool Publishers
Morgan Claypool Publishers
Morgan Claypool Publishers
w w w . m o r g a n c l a y p o o l . c o m
w w w . m o r g a n c l a y p o o l . c o m
w w w . m o r g a n c l a y p o o l . c o m
ISBN: 978-1-62705-115-6
ISBN: 978-1-62705-115-6
ISBN: 978-1-62705-115-6
90000
90000
90000
9 781627 051156
9 781627 051156
9 781627 051156
M
M
M
O
O
O
R
R
R
G
G
G
A
A
A
N
N
N
&
&
&
C
C
C
L
L
L
A
A
A
Y
Y
Y
P
P
P
O
O
O
O
O
O
L
L
L
SYNTHESIS LECTURES ON DATA MANAGEMENT
SYNTHESIS LECTURES ON DATA MANAGEMENT
SYNTHESIS LECTURES ON DATA MANAGEMENT
M. Tamer Özsu, Series Editor
M. Tamer Özsu, Series Editor
M. Tamer Özsu, Series Editor
Information and Influence
Propagation in
Social Networks
Synthesis Lectures on Data
Management
Editor
M. Tamer Özsu, University of Waterloo
Synthesis Lectures on Data Management is edited by Tamer Özsu of the University of Waterloo.
e series will publish 50- to 125 page publications on topics pertaining to data management. e
scope will largely follow the purview of premier information and computer science conferences, such
as ACM SIGMOD, VLDB, ICDE, PODS, ICDT, and ACM KDD. Potential topics include, but
not are limited to: query languages, database system architectures, transaction management, data
warehousing, XML and databases, data stream systems, wide scale data distribution, multimedia
data management, data mining, and related subjects.
Information and Influence Propagation in Social Networks
Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo
2013
Data Cleaning: A Practical Perspective
Venkatesh Ganti and Anish Das Sarma
2013
Data Processing on FPGAs
Jens Teubner and Louis Woods
2013
Perspectives on Business Intelligence
Raymond T. Ng, Patricia C. Arocena, Denilson Barbosa, Giuseppe Carenini, Luiz Gomes, Jr.
Stephan Jou, Rock Anthony Leung, Evangelos Milios, Renée J. Miller, John Mylopoulos, Rachel A.
Pottinger, Frank Tompa, and Eric Yu
2013
Semantics Empowered Web 3.0: Managing Enterprise, Social, Sensor, and Cloud-based
Data and Services for Advanced Applications
Amit Sheth and Krishnaprasad irunarayan
2012
Data Management in the Cloud: Challenges and Opportunities
Divyakant Agrawal, Sudipto Das, and Amr El Abbadi
2012
iii
Query Processing over Uncertain Databases
Lei Chen and Xiang Lian
2012
Foundations of Data Quality Management
Wenfei Fan and Floris Geerts
2012
Incomplete Data and Data Dependencies in Relational Databases
Sergio Greco, Cristian Molinaro, and Francesca Spezzano
2012
Business Processes: A Database Perspective
Daniel Deutch and Tova Milo
2012
Data Protection from Insider reats
Elisa Bertino
2012
Deep Web Query Interface Understanding and Integration
Eduard C. Dragut, Weiyi Meng, and Clement T. Yu
2012
P2P Techniques for Decentralized Applications
Esther Pacitti, Reza Akbarinia, and Manal El-Dick
2012
Query Answer Authentication
HweeHwa Pang and Kian-Lee Tan
2012
Declarative Networking
Boon au Loo and Wenchao Zhou
2012
Full-Text (Substring) Indexes in External Memory
Marina Barsky, Ulrike Stege, and Alex omo
2011
Spatial Data Management
Nikos Mamoulis
2011
Database Repairing and Consistent Query Answering
Leopoldo Bertossi
2011
iv
Managing Event Information: Modeling, Retrieval, and Applications
Amarnath Gupta and Ramesh Jain
2011
Fundamentals of Physical Design and Query Compilation
David Toman and Grant Weddell
2011
Methods for Mining and Summarizing Text Conversations
Giuseppe Carenini, Gabriel Murray, and Raymond Ng
2011
Probabilistic Databases
Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch
2011
Peer-to-Peer Data Management
Karl Aberer
2011
Probabilistic Ranking Techniques in Relational Databases
Ihab F. Ilyas and Mohamed A. Soliman
2011
Uncertain Schema Matching
Avigdor Gal
2011
Fundamentals of Object Databases: Object-Oriented and Object-Relational Design
Suzanne W. Dietrich and Susan D. Urban
2010
Advanced Metasearch Engine Technology
Weiyi Meng and Clement T. Yu
2010
Web Page Recommendation Models: eory and Algorithms
Sule Gündüz-Ögüdücü
2010
Multidimensional Databases and Data Warehousing
Christian S. Jensen, Torben Bach Pedersen, and Christian omsen
2010
Database Replication
Bettina Kemme, Ricardo Jimenez-Peris, and Marta Patino-Martinez
2010
v
Relational and XML Data Exchange
Marcelo Arenas, Pablo Barcelo, Leonid Libkin, and Filip Murlak
2010
User-Centered Data Management
Tiziana Catarci, Alan Dix, Stephen Kimani, and Giuseppe Santucci
2010
Data Stream Management
Lukasz Golab and M. Tamer Özsu
2010
Access Control in Data Management Systems
Elena Ferrari
2010
An Introduction to Duplicate Detection
Felix Naumann and Melanie Herschel
2010
Privacy-Preserving Data Publishing: An Overview
Raymond Chi-Wing Wong and Ada Wai-Chee Fu
2010
Keyword Search in Databases
Jeffrey Xu Yu, Lu Qin, and Lijun Chang
2009
Copyright © 2014 by Morgan & Claypool
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in
any form or by any means—electronic, mechanical, photocopy, recording, or any other except for brief quotations
in printed reviews, without the prior permission of the publisher.
Information and Influence Propagation in Social Networks
Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo
www.morganclaypool.com
ISBN: 9781627051156
ISBN: 9781627051163
paperback
ebook
DOI 10.2200/S00527ED1V01Y201308DTM037
A Publication in the Morgan & Claypool Publishers series
SYNTHESIS LECTURES ON DATA MANAGEMENT
Lecture #37
Series Editor: M. Tamer Özsu, University of Waterloo
Series ISSN
Synthesis Lectures on Data Management
Print 2153-5418 Electronic 2153-5426
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
