Influence Modeling and Malicious Users Identification in Interactive Networks

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.