File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Study of social-network-based information propagation

TitleStudy of social-network-based information propagation
Authors
Advisors
Advisor(s):Li, VOK
Issue Date2013
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Fan, X. [樊晓光]. (2013). Study of social-network-based information propagation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5089960
AbstractInformation propagation has attracted increasing attention from sociologists, marketing researchers and Information Technology entrepreneurs. With the rapid developments in online and mobile social applications like Facebook, Twitter, and LinkedIn, large-scale, high-speed and instantaneous information dissemination becomes possible, spawning tremendous opportunities for electronic commerce. It is non-trivial to make an accurate analysis on how information is propagated due to the uncertainty of human behavior and the complexity of the social environment. This dissertation is concerned with exploring models, formulations, and heuristics for the social-network-based information propagation process. It consists of three major parts: information diffusion through online social network, modeling social influence propagation, and social-network-based information spreading in opportunistic mobile networks. Firstly, I consider the problem of maximizing the influence propagation through online social networks. To solve it, I introduce a probabilistic maximum coverage problem, and propose a cluster-based heuristic and a neighbor-removal heuristic for two basic diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model, respectively. Realizing that the selection of influential nodes is mainly based on the accuracy and efficiency in estimating the social influence, I build a framework of up-to-2-hop hierarchical network to approximate the spreading of social influence, and further propose a hierarchy-based algorithm to solve the influence maximization problem. Our heuristic is proved to be efficient and robust with competitive performance, low computation cost, and high scalability. The second part explores the modeling on social influence propagation. I develop an analytical model for the influence propagation process based on discrete-time Markov chains, and deduce a close-form equation to express the n-step transition probability matrix. We show that given any initial state the probability distribution of the converged network state could be easily obtained by calculating a matrix product. Finally, I study the social-network-based information spreading in opportunistic mobile networks by analyzing the opportunistic routing process. I propose three social-network-based communication pattern models and utilize them to evaluate the performance of different social-network-based routing protocols based on several human mobility traces. Moreover, I discuss the fairness evaluation in opportunistic routing, and propose a fair packet forwarding strategy which operates as a plugin for traditional social- network-based routing protocols. My strategy improves the imbalance of success rates among users while maintaining approximately the same system throughput.
DegreeDoctor of Philosophy
SubjectOnline social networks.
Data mining.
Dept/ProgramElectrical and Electronic Engineering
Persistent Identifierhttp://hdl.handle.net/10722/192815

 

DC FieldValueLanguage
dc.contributor.advisorLi, VOK-
dc.contributor.authorFan, Xiaoguang.-
dc.contributor.author樊晓光.-
dc.date.accessioned2013-11-24T02:00:47Z-
dc.date.available2013-11-24T02:00:47Z-
dc.date.issued2013-
dc.identifier.citationFan, X. [樊晓光]. (2013). Study of social-network-based information propagation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5089960-
dc.identifier.urihttp://hdl.handle.net/10722/192815-
dc.description.abstractInformation propagation has attracted increasing attention from sociologists, marketing researchers and Information Technology entrepreneurs. With the rapid developments in online and mobile social applications like Facebook, Twitter, and LinkedIn, large-scale, high-speed and instantaneous information dissemination becomes possible, spawning tremendous opportunities for electronic commerce. It is non-trivial to make an accurate analysis on how information is propagated due to the uncertainty of human behavior and the complexity of the social environment. This dissertation is concerned with exploring models, formulations, and heuristics for the social-network-based information propagation process. It consists of three major parts: information diffusion through online social network, modeling social influence propagation, and social-network-based information spreading in opportunistic mobile networks. Firstly, I consider the problem of maximizing the influence propagation through online social networks. To solve it, I introduce a probabilistic maximum coverage problem, and propose a cluster-based heuristic and a neighbor-removal heuristic for two basic diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model, respectively. Realizing that the selection of influential nodes is mainly based on the accuracy and efficiency in estimating the social influence, I build a framework of up-to-2-hop hierarchical network to approximate the spreading of social influence, and further propose a hierarchy-based algorithm to solve the influence maximization problem. Our heuristic is proved to be efficient and robust with competitive performance, low computation cost, and high scalability. The second part explores the modeling on social influence propagation. I develop an analytical model for the influence propagation process based on discrete-time Markov chains, and deduce a close-form equation to express the n-step transition probability matrix. We show that given any initial state the probability distribution of the converged network state could be easily obtained by calculating a matrix product. Finally, I study the social-network-based information spreading in opportunistic mobile networks by analyzing the opportunistic routing process. I propose three social-network-based communication pattern models and utilize them to evaluate the performance of different social-network-based routing protocols based on several human mobility traces. Moreover, I discuss the fairness evaluation in opportunistic routing, and propose a fair packet forwarding strategy which operates as a plugin for traditional social- network-based routing protocols. My strategy improves the imbalance of success rates among users while maintaining approximately the same system throughput.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.source.urihttp://hub.hku.hk/bib/B50899600-
dc.subject.lcshOnline social networks.-
dc.subject.lcshData mining.-
dc.titleStudy of social-network-based information propagation-
dc.typePG_Thesis-
dc.identifier.hkulb5089960-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineElectrical and Electronic Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5089960-
dc.date.hkucongregation2013-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats