SmartWalk: Enhancing social network security via adaptive random walks

Yushan Liu, Shouling Ji, Prateek Mittal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations


Random walks form a critical foundation in many social network based security systems and applications. Currently, the design of such social security mechanisms is limited to the classical paradigm of using fixed-length random walks for all nodes on a social graph. However, the fixed-length walk paradigm induces a poor trade-off between security and other desirable properties. In this paper, we propose SmartWalk, a security enhancing system which incorporates adaptive random walks in social network security applications. We utilize a set of supervised machine learning techniques to predict the necessary random walk length based on the structural characteristics of a social graph. Using experiments on multiple real world topologies, we show that the desired walk length starting from a specific node can be well predicted given the local features of the node, and limited knowledge for a small set of training nodes. We describe node-adaptive and pathadaptive random walk usage models, where the walk length adaptively changes based on the starting node and the intermediate nodes on the path, respectively. We experimentally demonstrate the applicability of adaptive random walks on a number of social network based security and privacy systems, including Sybil defenses, anonymous communication and link privacy preserving systems, and show up to two orders of magnitude improvement in performance.

Original languageEnglish (US)
Title of host publicationCCS 2016 - Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)9781450341394
StatePublished - Oct 24 2016
Event23rd ACM Conference on Computer and Communications Security, CCS 2016 - Vienna, Austria
Duration: Oct 24 2016Oct 28 2016

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Other23rd ACM Conference on Computer and Communications Security, CCS 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'SmartWalk: Enhancing social network security via adaptive random walks'. Together they form a unique fingerprint.

Cite this