File Download
Supplementary

postgraduate thesis: Online influence maximization

TitleOnline influence maximization
Authors
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Lei, S. [雷思宇]. (2014). Online influence maximization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5446492
AbstractSocial networks, such as Twitter and Facebook, enable the wide spread of information through users’ influence on each other. These networks are very useful for marketing purposes. For example, free samples of a product can be given to a few influencers (seed nodes), with the hope that they will convince their friends to buy it. One way to formalize marketers’ objective is through the influence maximization problem, which is to find the best seed nodes to influence under a fixed budget so that the number of people who get influenced in the end is maximized. Recent solutions to influence maximization rely on the knowledge of the influence probability of every social network user. This is the probability that a user influences another one, and can be obtained by using users’ history of influencing others (called action logs). However, this information is not always available. We propose a novel Online Influence Maximization (OIM) framework, showing that it is possible to maximize influence in a social network in the absence of exact information about influence probabilities. In our OIM framework, we investigate an Explore-Exploit (EE) strategy, which could run any one of the existing influence maximization algorithms to select the seed nodes using the current influence probability estimation (exploit), or the confidence bound of the estimation (explore). We then start the influence campaign using the seed nodes, and consider users’ immediate feedback to the campaign to further decide which seed nodes to influence next. Influence probabilities are modeled as random variables and their probability distributions are updated as we get feedback. In essence, we perform influence maximization and learning of influence probabilities at the same time. We further develop an incremental algorithm that can significantly reduce the overhead of handling users’ feedback information. We validate the e↵ectiveness and efficiency of our OIM framework on large real-world datasets.
DegreeMaster of Philosophy
SubjectOnline social networks
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/210187

 

DC FieldValueLanguage
dc.contributor.authorLei, Siyu-
dc.contributor.author雷思宇-
dc.date.accessioned2015-05-26T23:10:10Z-
dc.date.available2015-05-26T23:10:10Z-
dc.date.issued2014-
dc.identifier.citationLei, S. [雷思宇]. (2014). Online influence maximization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5446492-
dc.identifier.urihttp://hdl.handle.net/10722/210187-
dc.description.abstractSocial networks, such as Twitter and Facebook, enable the wide spread of information through users’ influence on each other. These networks are very useful for marketing purposes. For example, free samples of a product can be given to a few influencers (seed nodes), with the hope that they will convince their friends to buy it. One way to formalize marketers’ objective is through the influence maximization problem, which is to find the best seed nodes to influence under a fixed budget so that the number of people who get influenced in the end is maximized. Recent solutions to influence maximization rely on the knowledge of the influence probability of every social network user. This is the probability that a user influences another one, and can be obtained by using users’ history of influencing others (called action logs). However, this information is not always available. We propose a novel Online Influence Maximization (OIM) framework, showing that it is possible to maximize influence in a social network in the absence of exact information about influence probabilities. In our OIM framework, we investigate an Explore-Exploit (EE) strategy, which could run any one of the existing influence maximization algorithms to select the seed nodes using the current influence probability estimation (exploit), or the confidence bound of the estimation (explore). We then start the influence campaign using the seed nodes, and consider users’ immediate feedback to the campaign to further decide which seed nodes to influence next. Influence probabilities are modeled as random variables and their probability distributions are updated as we get feedback. In essence, we perform influence maximization and learning of influence probabilities at the same time. We further develop an incremental algorithm that can significantly reduce the overhead of handling users’ feedback information. We validate the e↵ectiveness and efficiency of our OIM framework on large real-world datasets.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.subject.lcshOnline social networks-
dc.titleOnline influence maximization-
dc.typePG_Thesis-
dc.identifier.hkulb5446492-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats