We consider the Threshold Activation Problem (TAP): given social network @math and positive threshold @math , find a minimum-size seed set @math that can trigger expected activation of at least @math . We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter @math : given @math , with probability @math our algorithm returns a solution @math with expected activation greater than @math , and the size of the solution @math is within factor @math of the optimal size. The algorithm runs in time @math , where @math , @math , refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.
We propose DOCA (Detecting Overlapping Community Algorithm), a connection-based algorithm for discovering high quality overlapping community structures in social networks. Our proposed method is fast, very limited parameter dependent and only requires local knowledge about the network topology. Furthermore, the community structures discovered by DOCA are deterministic, i.e., no fuzzy community assignments are produced. DOCA's performance is certified by extensive experiments on real-world traces including Enron communication network, ArXiv citation and Astro physics collaboration networks as well as Face book and Foursquare social networks. The demonstrative benchmark with other detection methods highlights the efficiency of DOCA when discovering community structures of large-scale networks. By using DOCA to analyze the community structures of real datasets, we find that overlapping communities occur naturally and quite frequently, especially for top largest communities. In addition, overlapped nodes tend to be active users who participate in multiple communities at the same time. This happens not only on social networks but also on collaboration, citation and communication networks.  In this paper, we propose the amphibious influence maximization (AIM) model that combines traditional marketing via content providers and viral marketing to consumers in social networks in a single framework. In AIM, a set of content providers and consumers form a bipartite network while consumers also form their social network, and influence propagates from the content providers to consumers and among consumers in the social network following the independent cascade model. An advertiser needs to select a subset of seed content providers and a subset of seed consumers, such that the influence from the seed providers passing through the seed consumers could reach a large number of consumers in the social network in expectation. We prove that the AIM problem is NP-hard to approximate to within any constant factor via a reduction from Feige's k-prover proof system for 3-SAT5. We also give evidence that even when the social network graph is trivial (i.e. has no edges), a polynomial time constant factor approximation for AIM is unlikely. However, when we assume that the weighted bi-adjacency matrix that describes the influence of content providers on consumers is of constant rank, a common assumption often used in recommender systems, we provide a polynomial-time algorithm that achieves approximation ratio of (1-1 e-e)3 for any (polynomially small) e > 0. Our algorithmic results still hold for a more general model where cascades in social network follow a general monotone and submodular function. With the introduction of the World Wide Web and online social networks, people now have sought ways to socialize and make new friends online over a greater distance. Popular social network sites such as Facebook, Twitter and Bebo have witnessed rapid increases in space and the number of online users over a short period of time. However, alongside with these fast expands comes the threat of malicious softwares such as viruses, worms or false information propagation. In this paper, we propose a novel adaptive method for containing worm propagation on dynamic social networks. Our approach first takes into account the network community structure and adaptively keeps it updated as the social network evolves, and then contains worm propagation by distributing patches to most influential users selected from the network communities. To evaluate the performance of our approach we test it on Facebook network dataset [17] and compare the infection rates on several cases with the recent social-based method introduced in [21]. Experimental results show that our approach not only performs faster but also achieves lower infection rates than the social-based method on dynamic social networks.