1. bookVolume 2020 (2020): Edition 2 (April 2020)
Détails du magazine
Première parution
16 Apr 2015
4 fois par an
access type Accès libre

Identifying Influential Spreaders in a Social Network (While Preserving Privacy)

Publié en ligne: 08 May 2020
Volume & Edition: Volume 2020 (2020) - Edition 2 (April 2020)
Pages: 537 - 557
Reçu: 31 Aug 2019
Accepté: 16 Dec 2019
Détails du magazine
Première parution
16 Apr 2015
4 fois par an

In order to disseminate information in a social network, it is important to first identify the influential spreaders in the network. Using them as the seed spreaders, the aim is to ensure that the information is cascaded throughout the network. The traditional approach to identifying influential nodes is to determine the top-r ranked nodes in accordance with various ranking methods such as PageRank, k-Shell decomposition, ClusterRank and VoteRank. In the current work, we study the problem of ranking the nodes when the underlying graph is distributedly held by a set of individuals, who consider their share of the data as private information. In particular, we design efficient secure multiparty computation (MPC) protocols for k-Shell decomposition, PageRank and VoteRank. For improved efficiency, we employ the oblivious RAM construct in conjunction with efficient data-oblivious graph data structures. We are the first to propose a secure variant of the VoteRank algorithm. We prove that the proposed protocols are asymptotically more efficient and have lower runtime in practice than the previous best known MPC protocols for computing k-Shell decomposition and PageRank centrality scores.


[1] HuffPost-Staff. Whatsapp launches research grants up to $50,000 to fight fake news. [Online]. Available: https://www.huffingtonpost.in/2018/07/09/whatsapp-launches-research-grants-to-fight-misinformation-offering-up-to-50-000-per-proposal_a_23477400/Search in Google Scholar

[2] K. Bikoff. Sice receives $1.2 million as part of a darpa grant to study information spread. [Online]. Available: https://www.sice.indiana.edu/news/story.html?story=SICE-faculty-part-of-1.2-million-DARPA-grant-to-study-information-spreadSearch in Google Scholar

[3] J.-X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao, “Identifying a set of influential spreaders in complex networks,” Scientific reports, vol. 6, p. 27823, 2016.Search in Google Scholar

[4] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, “Epidemic processes in complex networks,” Reviews of modern physics, vol. 87, no. 3, p. 925, 2015.10.1103/RevModPhys.87.925Search in Google Scholar

[5] M. Yahya, “Polio vaccines- “no thank you!” barriers to polio eradication in northern nigeria,” African Affairs, vol. 106, no. 423, pp. 185–204, 2007.10.1093/afraf/adm016Search in Google Scholar

[6] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2003, pp. 137–146.10.1145/956750.956769Search in Google Scholar

[7] S. Aral and D. Walker, “Identifying influential and susceptible members of social networks,” Science, p. 1215842, 2012.Search in Google Scholar

[8] J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg, “Structural diversity in social contagion,” Proceedings of the National Academy of Sciences, p. 201116502, 2012.Search in Google Scholar

[9] E. Bakshy, I. Rosenn, C. Marlow, and L. Adamic, “The role of social networks in information diffusion,” in Proceedings of the 21st international conference on World Wide Web. ACM, 2012, pp. 519–528.10.1145/2187836.2187907Search in Google Scholar

[10] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Tech. Rep., 1999.Search in Google Scholar

[11] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, “Identification of influential spreaders in complex networks,” Nature physics, vol. 6, no. 11, p. 888, 2010.10.1038/nphys1746Search in Google Scholar

[12] J. Weng, E.-P. Lim, J. Jiang, and Q. He, “Twitterrank: finding topic-sensitive influential twitterers,” in Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010, pp. 261–270.10.1145/1718487.1718520Search in Google Scholar

[13] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009, pp. 199–208.10.1145/1557019.1557047Search in Google Scholar

[14] S. Ji, L. Lu, C. H. Yeung, and Y. Hu, “Effective spreading from multiple leaders identified by percolation in social networks,” arXiv preprint arXiv:1508.04294, 2015.Search in Google Scholar

[15] F. Kerschbaum, A. Schroepfer, A. Zilli, R. Pibernik, O. Catrina, S. de Hoogh, B. Schoenmakers, S. Cimato, and E. Damiani, “Secure collaborative supply-chain management,” Computer, no. 9, pp. 38–43, 2011.10.1109/MC.2011.224Search in Google Scholar

[16] G. Fridgen and T. Z. Garizy, “Supply chain network risk analysis-a privacy preserving approach.” in ECIS, 2015.Search in Google Scholar

[17] Y. Kim, T. Y. Choi, T. Yan, and K. Dooley, “Structural investigation of supply networks: A social network analysis approach,” Journal of Operations Management, vol. 29, no. 3, pp. 194–211, 2011.10.1016/j.jom.2010.11.001Search in Google Scholar

[18] M. Fire and R. Puzis, “Organization mining using online social networks,” Networks and Spatial Economics, vol. 16, no. 2, pp. 545–578, 2016.10.1007/s11067-015-9288-4Search in Google Scholar

[19] P. Glasserman and H. P. Young, “How likely is contagion in financial networks?” Journal of Banking & Finance, vol. 50, pp. 383–399, 2015.10.1016/j.jbankfin.2014.02.006Search in Google Scholar

[20] F. Kerschbaum and A. Schaad, “Privacy-preserving social network analysis for criminal investigations,” in Proceedings of the 7th ACM workshop on Privacy in the electronic society. ACM, 2008, pp. 9–14.10.1145/1456403.1456406Search in Google Scholar

[21] V. B. Kukkala and S. Iyengar, “Computing betweenness centrality: An efficient privacy-preserving approach,” in International Conference on Cryptology and Network Security. Springer, 2018, pp. 23–42.10.1007/978-3-030-00434-7_2Search in Google Scholar

[22] S. Zahur and D. Evans, “Obliv-c: A language for extensible data-oblivious computation.” IACR Cryptology ePrint Archive, vol. 2015, p. 1153, 2015.Search in Google Scholar

[23] A. C. Yao, “Protocols for secure computations,” in Foundations of Computer Science, 1982. SFCS’08. 23rd Annual Symposium on. IEEE, 1982, pp. 160–164.10.1109/SFCS.1982.38Search in Google Scholar

[24] J. Alwen, R. Ostrovsky, H.-S. Zhou, and V. Zikas, “Incoercible multi-party computation and universally composable receipt-free voting,” in Annual Cryptology Conference. Springer, 2015, pp. 763–780.10.1007/978-3-662-48000-7_37Search in Google Scholar

[25] A. Aly and M. Van Vyve, “Practically efficient secure single-commodity multi-market auctions,” in International Conference on Financial Cryptography and Data Security. Springer, 2016, pp. 110–129.10.1007/978-3-662-54970-4_7Search in Google Scholar

[26] S. Jha, L. Kruger, and V. Shmatikov, “Towards practical privacy for genomic computation,” in Security and Privacy, 2008. SP 2008. IEEE Symposium on. IEEE, 2008, pp. 216–230.10.1109/SP.2008.34Search in Google Scholar

[27] G. Asharov and Y. Lindell, “A full proof of the bgw protocol for perfectly secure multiparty computation,” Journal of Cryptology, vol. 30, no. 1, pp. 58–151, 2017.10.1007/s00145-015-9214-4Search in Google Scholar

[28] M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1988, pp. 1–10.10.1145/62212.62213Search in Google Scholar

[29] O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game,” in Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 1987, pp. 218–229.10.1145/28395.28420Search in Google Scholar

[30] A. C.-C. Yao, “How to generate and exchange secrets,” in Foundations of Computer Science, 1986., 27th Annual Symposium on. IEEE, 1986, pp. 162–167.Search in Google Scholar

[31] O. Goldreich and R. Ostrovsky, “Software protection and simulation on oblivious rams,” Journal of the ACM (JACM), vol. 43, no. 3, pp. 431–473, 1996.10.1145/233551.233553Search in Google Scholar

[32] B. Pinkas and T. Reinman, “Oblivious ram revisited,” in Annual Cryptology Conference. Springer, 2010, pp. 502–519.10.1007/978-3-642-14623-7_27Search in Google Scholar

[33] M. T. Goodrich and M. Mitzenmacher, “Privacy-preserving access of outsourced data via oblivious ram simulation,” in International Colloquium on Automata, Languages, and Programming. Springer, 2011, pp. 576–587.10.1007/978-3-642-22012-8_46Search in Google Scholar

[34] E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li, “Oblivious ram with o ((logn) 3) worst-case cost,” in International Conference on The Theory and Application of Cryptology and Information Security. Springer, 2011, pp. 197–214.10.1007/978-3-642-25385-0_11Search in Google Scholar

[35] E. Stefanov, E. Shi, and D. Song, “Towards practical oblivious ram,” arXiv preprint arXiv:1106.3652, 2011.Search in Google Scholar

[36] C. W. Fletcher, M. v. Dijk, and S. Devadas, “A secure processor architecture for encrypted computation on untrusted programs,” in Proceedings of the seventh ACM workshop on Scalable trusted computing. ACM, 2012, pp. 3–8.10.1145/2382536.2382540Search in Google Scholar

[37] M. Maas, E. Love, E. Stefanov, M. Tiwari, E. Shi, K. Asanovic, J. Kubiatowicz, and D. Song, “Phantom: Practical oblivious computation in a secure processor,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. ACM, 2013, pp. 311–324.10.1145/2508859.2516692Search in Google Scholar

[38] D. Apon, J. Katz, E. Shi, and A. Thiruvengadam, “Verifiable oblivious storage,” in International Workshop on Public Key Cryptography. Springer, 2014, pp. 131–148.10.1007/978-3-642-54631-0_8Search in Google Scholar

[39] M. Keller and P. Scholl, “Efficient, oblivious data structures for mpc,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2014, pp. 506–525.10.1007/978-3-662-45608-8_27Search in Google Scholar

[40] S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis, “Secure two-party computation in sublinear (amortized) time,” in Proceedings of the 2012 ACM conference on Computer and communications security. ACM, 2012, pp. 513–524.10.1145/2382196.2382251Search in Google Scholar

[41] C. Gentry, K. A. Goldman, S. Halevi, C. Julta, M. Raykova, and D. Wichs, “Optimizing oram and using it efficiently for secure computation,” in International Symposium on Privacy Enhancing Technologies Symposium. Springer, 2013, pp. 1–18.10.1007/978-3-642-39077-7_1Search in Google Scholar

[42] X. S. Wang, Y. Huang, T. H. Chan, A. Shelat, and E. Shi, “Scoram: oblivious ram for secure computation,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2014, pp. 191–202.10.1145/2660267.2660365Search in Google Scholar

[43] X. Wang, H. Chan, and E. Shi, “Circuit oram: On tightness of the goldreich-ostrovsky lower bound,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 2015, pp. 850–861.10.1145/2810103.2813634Search in Google Scholar

[44] S. Zahur, X. Wang, M. Raykova, A. Gascón, J. Doerner, D. Evans, and J. Katz, “Revisiting square-root oram: efficient random access in multi-party computation,” in Security and Privacy (SP), 2016 IEEE Symposium on. IEEE, 2016, pp. 218–234.10.1109/SP.2016.21Search in Google Scholar

[45] Keyhubs - uncover the hidden organization. [Online]. Available: http://www.keyhubs.com/Search in Google Scholar

[46] V. B. Kukkala, J. S. Saini, and S. Iyengar, “Privacy preserving network analysis of distributed social networks,” in International Conference on Information Systems Security. Springer, 2016, pp. 336–355.10.1007/978-3-319-49806-5_18Search in Google Scholar

[47] A. Aly and M. Van Vyve, “Securely solving classical network flow problems,” in International Conference on Information Security and Cryptology. Springer, 2014, pp. 205–221.10.1007/978-3-319-15943-0_13Search in Google Scholar

[48] A. Aly, E. Cuvelier, S. Mawet, O. Pereira, and M. Van Vyve, “Securely solving simple combinatorial graph problems,” in International Conference on Financial Cryptography and Data Security. Springer, 2013, pp. 239–257.10.1007/978-3-642-39884-1_21Search in Google Scholar

[49] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.Search in Google Scholar

[50] M. Ajtai, J. Komlós, and E. Szemerédi, “An 0 (n log n) sorting network,” in Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983, pp. 1–9.10.1145/800061.808726Search in Google Scholar

[51] K. E. Batcher, “Sorting networks and their applications,” in Proceedings of the April 30–May 2, 1968, spring joint computer conference. ACM, 1968, pp. 307–314.10.1145/1468075.1468121Search in Google Scholar

[52] M. T. Goodrich, “Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in o (n log n) time,” in Proceedings of the forty-sixth annual ACM symposium on Theory of computing. ACM, 2014, pp. 684–693.10.1145/2591796.2591830Search in Google Scholar

[53] M. T. Goodrich, “Randomized shellsort: A simple oblivious sorting algorithm,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010, pp. 1262–1277.10.1137/1.9781611973075.101Search in Google Scholar

[54] M. T. Goodrich, “Spin-the-bottle sort and annealing sort: Oblivious sorting via round-robin random comparisons,” in 2011 Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). SIAM, 2011, pp. 93–106.10.1137/1.9781611973013.11Search in Google Scholar

[55] S. B. Seidman, “Network structure and minimum degree,” Social networks, vol. 5, no. 3, pp. 269–287, 1983.10.1016/0378-8733(83)90028-XSearch in Google Scholar

[56] S. Pei and H. A. Makse, “Spreading dynamics in complex networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2013, no. 12, p. P12002, 2013.Search in Google Scholar

[57] V. Batagelj and M. Zaversnik, “An o (m) algorithm for cores decomposition of networks,” arXiv preprint cs/0310049, 2003.Search in Google Scholar

[58] R. S. Wahby, S. T. Setty, Z. Ren, A. J. Blumberg, and M. Walfish, “Efficient ram and control flow in verifiable outsourced computation.” in NDSS, 2015.10.14722/ndss.2015.23097Search in Google Scholar

[59] Q. Liu, B. Xiang, N. J. Yuan, E. Chen, H. Xiong, Y. Zheng, and Y. Yang, “An influence propagation view of pagerank,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 11, no. 3, p. 30, 2017.10.1145/3046941Search in Google Scholar

[60] N. Ma, J. Guan, and Y. Zhao, “Bringing pagerank to the citation analysis,” Information Processing & Management, vol. 44, no. 2, pp. 800–810, 2008.10.1016/j.ipm.2007.06.006Search in Google Scholar

[61] T. Tassa and F. Bonchi, “Privacy preserving estimation of social influence.” in EDBT, 2014, pp. 559–570.Search in Google Scholar

[62] V. Kolesnikov and T. Schneider, “Improved Garbled Circuit: Free XOR Gates and Applications,” in International Colloquium on Automata, Languages, and Programming. Springer, 2008, pp. 486–498.10.1007/978-3-540-70583-3_40Search in Google Scholar

[63] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner, “More Efficient Oblivious Transfer and Extensions for Faster Secure Computation,” in SIGSAC Conference on Computer & Communications Security. ACM, 2013, pp. 535–548.10.1145/2508859.2516738Search in Google Scholar

[64] S. Zahur, M. Rosulek, and D. Evans, “Two Halves Make a Whole,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2015, pp. 220–250.10.1007/978-3-662-46803-6_8Search in Google Scholar

[65] M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway, “Efficient Garbling from a Fixed-key Blockcipher,” in Security and Privacy (SP). IEEE, 2013, pp. 478–492.10.1109/SP.2013.39Search in Google Scholar

[66] J. Doerner, “The Absentminded Crypto Kit,” “https://bitbucket.org/jackdoerner/absentminded-crypto-kit.git”.Search in Google Scholar

[67] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” science, vol. 286, no. 5439, pp. 509–512, 1999.Search in Google Scholar

[68] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821–7826, 2002.Search in Google Scholar

[69] S. Fortunato, “Community detection in graphs,” Physics reports, vol. 486, no. 3-5, pp. 75–174, 2010.10.1016/j.physrep.2009.11.002Search in Google Scholar

[70] S. P. Borgatti and M. G. Everett, “Models of core/periphery structures,” Social networks, vol. 21, no. 4, pp. 375–395, 2000.10.1016/S0378-8733(99)00019-2Search in Google Scholar

[71] J. Travers and S. Milgram, “The small world problem,” Phychology Today, vol. 1, no. 1, pp. 61–67, 1967.Search in Google Scholar

[72] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” nature, vol. 393, no. 6684, p. 440, 1998.Search in Google Scholar

[73] T. Y. Choi and Y. Hong, “Unveiling the structure of supply networks: case studies in honda, acura, and daimlerchrysler,” Journal of Operations Management, vol. 20, no. 5, pp. 469–493, 2002.10.1016/S0272-6963(02)00025-6Search in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo