1. bookVolume 2020 (2020): Issue 2 (April 2020)
Zeitschriftendaten
License
Format
Zeitschrift
Erstveröffentlichung
16 Apr 2015
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
access type Open Access

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

Online veröffentlicht: 08 May 2020
Seitenbereich: 537 - 557
Eingereicht: 31 Aug 2019
Akzeptiert: 16 Dec 2019
Zeitschriftendaten
License
Format
Zeitschrift
Erstveröffentlichung
16 Apr 2015
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch

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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search in Google Scholar

[32] B. Pinkas and T. Reinman, “Oblivious ram revisited,” in Annual Cryptology Conference. Springer, 2010, pp. 502–519.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search in Google Scholar

[55] S. B. Seidman, “Network structure and minimum degree,” Social networks, vol. 5, no. 3, pp. 269–287, 1983.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo