No description available.

Social 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. / published_or_final_version / Computer Science / Master / Master of Philosophy

之前和社交網絡相關的研究，大多數都非常關注積極正面的用戶鏈接關係；與這些研究不同，我們研究同時含有正面與負面鏈接關係的帶符號社交網絡。具體來講，我們特別關注如何在一個帶符號的社交網絡（該網絡又稱為“目標網絡“）中可信並且有效地去預測鏈接關係的符號為正或是為負，且該網絡中僅有一小部份的鏈接關係符號已知，作為訓練樣本。我們採取遷移學習的機器學習方法，借助於另外一個帶符號社交網絡（該網絡又稱為“源網絡“）中充足的鏈接關係符號信息，從而訓練得到一個有效的鏈接關係分類器；需要注意的是，該 “源網絡同“目標網絡，在鏈接關係樣本和鏈接關係符號的聯合分佈上，並不相同。 / 由於在帶符號社交網絡中沒有事先定義好的屬性向量，我們需要構造一種普適的屬性特徵，從而可以把“源網絡“的拓撲結構信息有效地遷移到“目標網絡“中去。借助於構造好的普適屬性，我們使用了一種類似AdaBoost的遷移學習算法，通過調整訓練樣本的權重，從而可以更好地利用“源網絡“中的樣本信息輔助模型的學習。我們使用兩個真實的大型帶符號社交網絡進行實驗，結果顯示我們的遷移學習算法可以較基準方案，在鏈接關係符號預測的準確度上，提高百分之四十。 / Different from a large body of research on social networks that almost exclusively focused on positive relationships, we study signed social networks with both positive and negative links. Specifically, we focus on how to reliably and effectively predict the signs of links in a signed social network (called a target network), where a very small amount of edge sign information is available as the training data. To train a good classifier, we adopt the transfer learning approach to leverage the abundant edge signs from another signed social network (called a source network) which may have a different joint distribution of the observed instance and the class label. / As there is no predefined feature vector for the edge instances in a signed network, we construct generalizable features that can transfer the topological knowledge from the source network to the target. With the extracted features, we adopt an AdaBoost-like transfer learning algorithm with instance weighting to utilize more useful training instances in the source network for model learning. Experimental results on two real large signed social networks demonstrate that our transfer learning algorithm can improve the prediction accuracy by 40% over baseline schemes. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Ye, Jihang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 51-56). / Abstracts also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Work --- p.8 / Chapter 3 --- Problem Formulation --- p.13 / Chapter 4 --- Feature Construction --- p.16 / Chapter 4.1 --- Explicit Topological Features --- p.17 / Chapter 4.2 --- Latent Topological Feature --- p.19 / Chapter 4.2.1 --- Optimization Algorithm --- p.22 / Chapter 4.2.2 --- Convergence Analysis --- p.23 / Chapter 5 --- Edge Sign Prediction by Transfer Learning --- p.28 / Chapter 5.1 --- Transfer Learning with Instance Weighting --- p.29 / Chapter 5.2 --- Training Loss Analysis --- p.31 / Chapter 6 --- Experimental Evaluation --- p.35 / Chapter 6.1 --- Data Preparation --- p.35 / Chapter 6.2 --- Evaluation of Transfer Learning with InstanceWeighting --- p.37 / Chapter 6.3 --- Effectiveness of Topological Features --- p.41 / Chapter 7 --- Conclusion --- p.45 / Chapter A --- Proof of Theorem 1 --- p.48 / Bibliography --- p.51

The rapid development of online social networks (OSNs) renders them a powerful platform for information diffusion on a massive scale. OSNs generate enormous propagation traces. An important question is how to model the real-world information diffusion process. Although considerable studies have been conducted in this field, the temporal characteristics have not been fully addressed yet. This thesis addresses the issue of modeling the temporal dynamics of the information diffusion process. Based on empirical findings drawn from large-scale propagation traces of a popular OSN in China, we demonstrate that the temporal characteristics has a significant impact on the diffusion dynamics. Hence, a series of new temporal information diffusion models have been proposed by incorporating these temporal features. Experimental results demonstrate that these proposed models are more accurate and practical than existing discrete diffusion models. Moreover, one application of information diffusion models, i.e., the revenue maximization problem, is studied. Specifically, the thesis consists of three major parts: 1) preliminaries, i.e., introduction of research platform and collected dataset, 2) modeling social influence diffusion from three different temporal aspects, and 3) monetizing OSNs through designing intelligent pricing strategies in the diffusion process to realize the goal of revenue maximization. Firstly, the research platform is introduced and the statistical properties of the data derived from this platform are investigated. We choose Renren, the dominant social network website in China, as our research platform and study its information propagation mechanisms. Specifically, we concentrate on the propagation of “sharing video” behaviors, and collect data on more than 2.8 million Renren users and over 209 million diffusion traces. The analysis result shows that the video access patterns in OSNs differ significantly from Youtube-like systems, which makes understanding the video propagation behaviors in OSNs an important research task. Secondly, the temporal modeling of information diffusion is explored. By investigating temporal features using real diffusion traces, we find that three factors should be considered in building realistic diffusion models, including, information propagation latency, multiple influential sources and user diversities. We then develop models to explain the information propagation process by incorporating these factors, and demonstrate that the models reflect reality well. Finally, revenue maximization in the information diffusion process is studied. Specifically, the pricing factor is explicitly incorporated into the product diffusion process. To realize the goal of revenue maximization, we develop a Dynamic Programming Based Heuristic (DPBH) to obtain the optimal pricing sequence. Application of the DPBH in the revenue maximization problem shows that it performs well in both the expected revenue achieved and in running time. This leads to fundamental ramifications to many related OSN marketing applications. / published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Information diffusion in online social networks has received attention in both research and actual applications. The prevalence of online social networking sites offers the possibility of mining for necessary information. However, existing influence maximization algorithms and newly proposed influence diffusion models do not distinguish between seed nodes (or pilot users) and nonseed nodes and assume all nodes are cooperative in propagating influence. This thesis investigates models and heuristics for noncooperative information diffusion in online social networks. It consists of three parts: tragedy of the commons in online social search (OSS), influence maximization in noncooperative social networks under the linear threshold model (LTM), and influence maximization in noncooperative social networks under the independent cascade model (ICM). Firstly, the tragedy of the commons problem in OSS is considered. I propose an analytical model that captures the behavior of OSS nodes, and, from a gaming-strategy point of view, analyze various strategies an individual node can utilize to allocate its awareness capacity. Based on this I derive the Pareto inefficiency in terms of the system cost. An incentive scheme which can lead selfish nodes to the “social optimal” state of the whole system is also proposed. Extensive simulations show that the strategy with our proposed incentive mechanism outperforms other strategies in terms of the system cost and the search success rate. The second part of the thesis presents the first detailed analysis of influence maximization in noncooperative social networks under the LTM. The influence propagation process is structured into two stages, namely, seed node selection and influence diffusion. In the former, I introduce a generalized maximum-flow-based analytical framework to model the noncooperative behavior of individual users and develop a new seed node selection strategy. In the latter, I propose a game-theoretic model to characterize the behavior of noncooperative nodes and design a Vickrey-Clarke-Groves-like (VCG-like) scheme to incentivise cooperation. Then I study the budget allocation problem between the two stages, and show that a marketer can utilize the two proposed strategies to tackle noncooperation intelligently. The proposed schemes are evaluated on large coauthorship networks, and the results show that the proposed seed node selection scheme is very robust to noncooperation and the VCG-like scheme can effectively stimulate a node to become cooperative. Finally, I study the influence maximization problem in noncooperative social networks under the ICM using the same two-stage framework originally proposed for LTM. For the seed selection stage, a modified hierarchy-based seed node selection strategy which can take node noncooperation into consideration is introduced. The VCG-like incentive scheme designed for the influence diffusion stage under LTM can also be utilized for ICM in a similar manner. Then I also study the budget allocation problem between the two stages. The evaluation results show that the performance of the hierarchy-based seed node selection scheme is satisfactory in a noncooperative social network and the VCG-like scheme can effectively encourage node cooperation. / published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Thesis (M.S.)--Kent State University, 2007. / Title from PDF t.p. (viewed Nov. 20, 2007). Advisor: Javed I Khan. Includes bibliographical references (p. 99-101).

Thesis (M.A.)--George Mason University, 2008. / Vita: p. 61. Thesis director: Byron Hawk. Submitted in partial fulfillment of the requirements for the degree of Master of Arts in English. Title from PDF t.p. (viewed July 2, 2008). Includes bibliographical references (p. 54-60). Also issued in print.

Thesis (PhD) -- AUT University, 2008. / Includes bibliographical references. Also held in print (xix, 361 p. : ill. ; 30 cm.) in the Archive at the City Campus (T 302.30285 THO)

The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file. Title from PDF of title page (University of Missouri--Columbia, viewed on September 25, 2009). Thesis advisor: Dr. Shelly Rodgers. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.