由於在線社交網絡的龐大用戶群和口碑效應的病毒式傳播特點，使用少量用戶吸引大量用戶的定向廣告策略在病毒營銷中是非常有效的。公司可以先提供免費商品給在線社交網絡上的小部份用戶，然後依靠這些用戶推薦此產品給他們的好友，從而達到提升產品整體銷售額的目的。在本文中，我們考慮如下在線社交網絡中廣告投放的問題:給定廣告投放資本，比如固定數目的免費產品，公司需要決定在線社交網絡中用戶會最終購買的概率。為了研究此問題，我們把在線社交網絡模擬成擁有或者沒有高聚合係數的無標度圖。我們使用多個影響機制來刻畫如此大規模網絡中的影響傳播，并且使用本地平均場技術來分析這些節點狀態會被影響機制所改變的網絡。我們運行了大量的仿真實驗來驗證我們的理論模型。這些模型能夠為設計在線社交網絡中的有效廣告投放策略提供認識和指導。 / 雖然口碑效應的病毒式傳播能有效地促進產品銷售，但是它同時也為惡意行為提供了機會:不誠實用戶會故意給他們的好友提供錯誤的推薦從而擾亂正常的市場份額分配。為了解決這個問題，我們提出了一個通用的檢測框架，并基於此檢測框架制定了一系列完全分佈式的檢測算法來識別在線社交網絡中的不誠實用戶。我們考慮了不誠實用戶採取基本策略和智能策略兩種情況。我們通過計算假陽性概率，假陰性概率和檢測不誠實用戶所需要的時間的分佈來度量檢測算法的性能。大量的仿真實驗不僅說明了不誠實推薦所造成的影響，也驗證了檢測算法的有效性。我們還應用前面提到的通用檢測框架來解決無線網格網絡(wireless mesh network)和點對點視頻直播網絡(peer-to-peer live streaming network)中的污染攻擊問題。在應用了網絡編碼的無線網格網絡中，污染攻擊是一個很嚴重的安全問題。惡意節點能夠輕易地發動污染攻擊，從而造成污染數據包的病毒式傳播進而消耗網絡資源。前面提到的通用檢測框架也能被用來解決此安全問題。明確地說，我們使用基於時間的校驗碼和批量驗證機制來決定污染數據包的存在與否，然後提出一系列完全分佈式的檢測算法。即使智能攻擊者存在時，此檢測算法仍然有效。這裡智能攻擊者指的是那些為了降低被檢測到的概率從而假裝合法節點傳輸有效數據包的節點。並且，為了解決攻擊者合作注入污染數據包的情形并加速檢測，我們還提出了一個增強的檢測算法。我們也給出了規範的分析來度量檢測算法的性能。最後，仿真實驗和系統原型驗證了我們的理論分析以及檢測算法的有效性。 / 污染攻擊還會對點對點視頻直播網絡基礎設施造成嚴重影響，比如說，它能夠減少網絡中的攻擊問題，我們仍然基於前面提到的通用檢測框架提出了分佈式的檢測算法來識別污染攻擊者。我們也提供了理論分析來度量檢測算法的性能從而證明了算法的有效性。 / Due to the large population in online social networks and the epidemic spreading of word-of-mouth effect, targeted advertisement which use a small fraction of buyers to attract a large population of buyers is very efficient in viral marketing, for example, companies can provide incentives (e.g., via free samples of a product) to a small group of users in an online social network, and these users can provide recommendations to their friends so as to increase the overall sales of the product. In particular, we consider the following advertisement problem in online social networks: given a fixed advertisement investment, e.g., a number of free samples, a company needs to determine the probability that users in the online social network will eventually purchase the product. To address this problem, we model online social networks as scale-free graphs with/without high clustering coefficient. We employ various influence mechanisms that govern the influence spreading in such large scale networks and use the local mean field technique to analyze them wherein states of nodes can be changed by various influence mechanisms. We carry out extensive simulations to validate our models which can provide insight on designing efficient advertising strategies in online social networks. / Although epidemic spreading of word-of-mouth effect can increase the sales of a product efficiently in viral marketing, it also opens doors for “malicious behaviors: dishonest users may intentionally give wrong recommendations to their friends so as to distort the normal sales distribution. To address this problem, we propose a general detection framework and develop a set of fully distributed detection algorithms to discover dishonest users in online social networks by applying the general detection framework. We consider both cases when dishonest users adopt (1) baseline strategy, and (2) intelligent strategy. We quantify the performance of the detection algorithms by deriving probability of false positive, probability of false negative and distribution function of time needed to detect dishonest users. Extensive simulations are carried out to illustrate the impact of dishonest recommendations and the effectiveness of the detection algorithms. / We also apply the general detection framework to address the problem of pollution attack in wireless mesh networks (WMNs) and peer-to-peer (P2P) streaming networks. Epidemic attack is a severe security problem in network-coding enabled wireless mesh networks, and malicious nodes can easily launch such form of attack to create an epidemic spreading of polluted packets and deplete network resources. The general detection framework can also be applied to address such security problem. Specifically, we employ the time-based checksum and batch verification to determine the existence of polluted packets, then propose a set of fully distributed detection algorithms. We also allow the presence of “smart attackers, i.e., they can pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. To address the case when attackers cooperatively inject polluted packets and speed up the detection, an enhanced detection algorithm is also developed. Furthermore, we provide formal analysis to quantify the performance of the detection algorithms. At last, simulations and system prototyping are also carried out to validate the theoretic analysis and show the effectiveness and efficiency of the detection algorithms. / To address the problem of pollution attack in P2P streaming networks, which is known to have a disastrous effect on existing P2P infrastructures, e.g., it can reduce the number of legitimate users by as much as 85%, we also propose distributed detection algorithms to identify pollution attackers by applying the general framework. Moreover, we provide theoretical analysis to quantify the performance of the detection algorithms so as to show their effectiveness and efficiency. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Yongkun. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 148-157). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Influence Modeling in Online Social Networks --- p.7 / Chapter 2.1 --- Scale-free Graphs without High Clustering Coefficient --- p.8 / Chapter 2.1.1 --- Modeling Online Social Networks --- p.8 / Chapter 2.1.2 --- q-influence Model --- p.11 / Chapter 2.1.3 --- m-threshold Influence Model --- p.14 / Chapter 2.1.4 --- Majority Rule Influence Model --- p.16 / Chapter 2.2 --- Scale-free Graphs with High Clustering Coefficient --- p.19 / Chapter 2.3 --- Generalized Influence Models --- p.21 / Chapter 2.3.1 --- Deterministic Influence Model --- p.21 / Chapter 2.3.2 --- Probabilistic Influence Model --- p.25 / Chapter 2.4 --- Multi-state Model --- p.27 / Chapter 2.4.1 --- Example of 3-State Majority Rule --- p.32 / Chapter 3 --- Identifying Dishonest Recommenders in Online Social Networks --- p.35 / Chapter 3.1 --- General Detection Framework --- p.37 / Chapter 3.2 --- Modeling the Behaviors of Users --- p.41 / Chapter 3.2.1 --- Products and Recommendations --- p.41 / Chapter 3.2.2 --- Behaviors of Users --- p.43 / Chapter 3.3 --- Distributed Detection Algorithms --- p.45 / Chapter 3.3.1 --- Identifying Dishonest Recommenders when Baseline Strategy is Adopted --- p.46 / Chapter 3.3.2 --- Identifying Dishonest Recommenders when Intelligent Strategy is Adopted --- p.53 / Chapter 3.3.3 --- Complete Detection Algorithm --- p.57 / Chapter 3.4 --- Cooperative Algorithm to Speed up the Detection --- p.58 / Chapter 3.5 --- Algorithm Dealing with User Churn --- p.61 / Chapter 4 --- Identifying Pollution Attackers in Network Coding Enabled Wireless Mesh Networks --- p.64 / Chapter 4.1 --- Introduction on Wireless Mesh Networks and Pollution Attack --- p.64 / Chapter 4.2 --- Network Coding and Time-based Checksum Batch Verification --- p.66 / Chapter 4.3 --- Basic Detection Algorithms --- p.70 / Chapter 4.3.1 --- Core Idea of the Detection Algorithms --- p.71 / Chapter 4.3.2 --- Attackers with Imitation Probability δ = 0 --- p.74 / Chapter 4.3.3 --- Attackers with Imitation Probability δ > 0 --- p.78 / Chapter 4.3.4 --- Improvement on Probability of False Negative --- p.81 / Chapter 4.4 --- Enhanced Detection Algorithm --- p.82 / Chapter 4.4.1 --- Detection Algorithm --- p.82 / Chapter 4.4.2 --- Performance Analysis --- p.87 / Chapter 4.4.3 --- Detection Acceleration --- p.91 / Chapter 4.5 --- Alternative Detection Algorithms --- p.92 / Chapter 5 --- Identifying Pollution Attackers in Peer-to-Peer Live Streaming Systems --- p.95 / Chapter 5.1 --- Introduction on Peer-to-Peer Streaming Systems and the Problem of Pollution Attack --- p.95 / Chapter 5.2 --- Detection Algorithms --- p.97 / Chapter 5.2.1 --- Imitation Probability δ = 0 --- p.99 / Chapter 5.2.2 --- Imitation Probability δ > 0 --- p.102 / Chapter 5.2.3 --- Improvement on Probability of False Negative --- p.104 / Chapter 6 --- Performance Evaluation --- p.106 / Chapter 6.1 --- Influence Modeling in Online Social Networks --- p.107 / Chapter 6.1.1 --- Online Social Networks without High Clustering Coefficient --- p.107 / Chapter 6.1.2 --- Online Social Networks with High Clustering Coefficient --- p.113 / Chapter 6.1.3 --- Performance Evaluation of the Multi-state Model --- p.116 / Chapter 6.2 --- Performance Evaluation of the Detection Algorithms in Online Social Networks --- p.118 / Chapter 6.2.1 --- Synthesizing Dynamically Evolving Online Social Networks --- p.118 / Chapter 6.2.2 --- Impact of Wrong Recommendations --- p.120 / Chapter 6.2.3 --- Performance Evaluation of the Detection Algorithms --- p.121 / Chapter 6.3 --- Performance Evaluation of the Detection Algorithms in Wireless Mesh Networks --- p.126 / Chapter 6.3.1 --- Performance of the Basic Detection Algorithms --- p.126 / Chapter 6.3.2 --- Results from System Prototype --- p.131 / Chapter 6.3.3 --- Performance of the Enhanced Detection Algorithm --- p.132 / Chapter 6.4 --- Performance Evaluation of the Detection Algorithms in Peer-topeer Streaming Networks --- p.136 / Chapter 6.4.1 --- Performance of the Baseline Algorithm --- p.136 / Chapter 6.4.2 --- Performance of the Randomized Algorithm --- p.138 / Chapter 6.4.3 --- Derive Optimal Uploading Probability --- p.141 / Chapter 7 --- RelatedWork and Conclusion --- p.143
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328158 |
| Date | January 2012 |
| Contributors | Li, Yongkun., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (xiv, 157 leaves) : ill. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.3508 seconds