2015 EfficientAlgorithmsforPublicPri

• (Chierichetti et al., 2015) ⇒ Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, and Vahab Mirrokni. (2015). “Efficient Algorithms for Public-Private Social Networks.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783354

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Efficient+Algorithms+for+Public-Private+Social+Networks
• http://dl.acm.org/citation.cfm?id=2783258.2783354&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; graph algorithms; graph algorithms; privacy; social networks

Abstract

We introduce the public-private model of graphs. In this model, we have a public graph and each node in the public graph has an associated private graph. The motivation for studying this model stems from social networks, where the nodes are the users, the public graph is visible to everyone, and the private graph at each node is visible only to the user at the node. From each node's viewpoint, the graph is just a union of its private graph and the public graph.

We consider the problem of efficiently computing various properties of the graphs from each node's point of view, with minimal amount of recomputation on the public graph. To illustrate the richness of our model, we explore two powerful computational paradigms for studying large graphs, namely, sketching and sampling, and focus on some key problems in social networks and show efficient algorithms in the public-private graph model. In the sketching model, we show how to efficiently approximate the neighborhood function, which in turn can be used to approximate various notions of centrality. In the sampling model, we focus on all-pair shortest path distances, node similarities, and correlation clustering.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 EfficientAlgorithmsforPublicPri	Flavio Chierichetti Ravi Kumar Silvio Lattanzi Vahab Mirrokni Alessandro Epasto			Efficient Algorithms for Public-Private Social Networks				10.1145/2783258.2783354		2015