EE Seminar: Secure Computation of Social Prestige and Influence from Multiple Networks

~~(The talk will be given in English)

Speaker:   Prof. Tamir Tassa
                       The Department of Mathematics and Computer Science, Open University

Monday, May 30, 2016
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

Secure Computation of Social Prestige and Influence from Multiple Networks

Abstract

We study the problem of computing social prestige measures over multiple networks. We consider a setting in which there are several mutually non-trusting parties (called hosts), each one of them holding a proprietary social network on the same ground set of users (nodes). Those hosts wish to compute a prestige (or centrality) score for each of the users, without disclosing information about their private graphs.

We study three measures of prestige, one progressively extending the previous. The first measure counts the number of nodes reachable from a node within a given radius. The second measure, corresponding to the classic Katz score [L. Katz, A new status index derived from sociometric index, Psychometrika, 1953], extends the first one by counting the number of paths between any two nodes. The final one is an original extension of the Katz score to the multigraph case: not only the number of paths are counted, but also the multiplicity of these paths in the different networks is taken into consideration.

We then present a suite of multiparty protocols to compute the three measure of prestige. We show that our protocols are secure in the information-theoretic sense. We also study how to scale our protocols to very large graphs. Finally, we test our protocols on several real-world multigraphs: interestingly, the protocol to compute the most sensitive score (i.e., the multigraph prestige measure) is also the most scalable one and can be efficiently run on very large networks.

Joint work with Gilad Asharov, Francesco Bonchi, and David Garcia-Soriano

Bio:
Tamir Tassa is currently an associate professor in the Department of Mathematics and Computer Science at the Open University of Israel. Previously, he served as a lecturer and researcher in the School of Mathematical Sciences at Tel Aviv University, and in the Department of Computer Science at Ben Gurion University. During the years 1993-1996 he served as an assistant professor of Computational and Applied Mathematics at the University of California, Los Angeles. He earned his PhD in applied mathematics from the Tel Aviv University in 1993. His recent research interests include privacy-preserving data publishing and data mining, secure multi-party computation, secret sharing, and combinatorial optimization.