Abstract
As an imperative channel for fast information propagation, online social networks (OSNs) also have their defects. One of them is the information leakage, i.e., information could be spread via OSNs to the users whom we are not willing to share with. Thus the problem of constructing a circle of trust to share information with as many friends as possible without further spreading it to unwanted targets has become a challenging research topic but still remained open. Our work is the first attempt to study the Maximum Circle of Trust problem seeking to share the information with the maximum expected number of poster’s friends such that the information spread to the unwanted targets is brought to its knees. First, we consider a special and more practical case with the two-hop information propagation and a single unwanted target. In this case, we show that this problem is NP-hard, which denies the existence of an exact polynomial-time algorithm. We thus propose a Fully Polynomial-Time Approximation Scheme (FPTAS), which can not only adjust any allowable performance error bound but also run in polynomial time with both the input size and allowed error. FPTAS is the best approximation solution one can ever wish for an NP-hard problem. We next consider the number of unwanted targets is bounded and prove that there does not exist an FPTAS in this case. Instead, we design a Polynomial-Time Approximation Scheme (PTAS) in which the allowable error can also be controlled. When the number of unwanted targets are not bounded, we provide a randomized algorithm, along with the analytical theoretical bound and inapproximaibility result. Finally, we consider a general case with many hops information propagation and further show its #P-hardness and propose an effective Iterative Circle of Trust Detection (ICTD) algorithm based on a novel greedy function. An extensive experiment on various real-world OSNs has validated the effectiveness of our proposed approximation and ICTD algorithms. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.
Similar content being viewed by others
References
Cha M, Haddadi H, Benevenuto F, Gummadi KP (2010) Measuring user influence in twitter: the million follower fallacy. In: Proceedings of the 4th international AAAI conference on weblogs and social media (ICWSM), May
Cha M, Mislove A, Gummadi KP (2009) A measurement-driven analysis of information propagation in the flickr social network. In: Proceedings of the 18th international conference on world wide web, WWW ’09, NY, USA. ACM, New York, pp 721–730
Colbourn CJ (1987) The combinatorics of network reliability. Oxford University Press, New York
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Series of books in the mathematical sciences, 1st edn. W. H. Freeman, New York
Gjoka M, Kurant M, Butts CT (2010) Markopoulou a walking in facebook: a case study of unbiased sampling of OSNs. In: Proceedings of IEEE INFOCOM 2010. IEEE, New York, pp 1–9
Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420
Hastad J (1996) Clique is hard to approximate within \(n^{1-\epsilon }\). In: FOCS ’96. IEEE Computer Society, Washington, DC, p 627
Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’03. ACM, New York, pp 137–146
Lam I-F, Chen K-T, Chen L-J (2008) Involuntary information leakage in social network services. In: Proceedings of the 3rd international workshop on security: advances in information and computer security, IWSEC ’08. Springer, Berlin, pp 167–183
Luenberger DG (2003) Linear and nonlinear programming, 2nd edn. Springer, New York
Megiddo N, Tamir A (1993) Linear time algorithms for some separable quadratic programming problems. Oper Res Lett 13:203–211
Ngoc TH, Echizen I, Komei K, Yoshiura H (2010) New approach to quantification of privacy on social network sites. In: Proceedings of the 2010 24th IEEE international conference on advanced information networking and applications, AINA ’10. IEEE Computer Society, Washington, DC, pp 556–564
Nigusse G, Decker BD (2010) Privacy codes of practice for the social web: the analysis of existing privacy codes and emerging social-centric privacy risks. In: AAAI spring symposium series
Raghavan P (1988) Probabilistic construction of deterministic algorithms: approximating packing integer programs. J Comput Syst Sci 37:130–143
Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of WOSN’09
Walters ST, Neighbors C (2005) Feedback interventions for college alcohol misuse: what, why and for whom? Addict Behav 30(6):1168–1182
Acknowledgments
This work is partially supported by NSF Career Award # 0953284, DTRA, Young Investigator Award, Basic Research Program # HDTRA1-09-1-0061 and DTRA # HDTRA1-08-10.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shen, Y., Dinh, T.N., Thai, M.T. et al. Staying safe and visible via message sharing in online social networks. J Comb Optim 28, 186–217 (2014). https://doi.org/10.1007/s10878-013-9667-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9667-z