Top

Social Network Analysis and Mining

Published in:

01-12-2015 | Original Article

Sharding distributed social databases using social network analysis

Authors: Pranav Thulasiram Bhat, Rohit Varkey Thankachan, K. Chandrasekaran

Published in: Social Network Analysis and Mining | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Social networking services support millions of users who interact with one another on a regular basis and generate substantial amounts of data. Due to the inherently distributed structure of such networks and the possible remoteness of the users, the data involved must be partitioned into shards and distributed over a number of servers. One of the most important functionalities of a social networking platform is to process queries related, not only to a given users data but also to the users acquaintances. This suggests that a competent sharding algorithm for a distributed social database must make use of the social network’s topology. We describe algorithms that utilize the structure of social networks to prepare shards that result in better query performance, lower network utilization and better load balancing.

previous article Deception detection in Twitter

next article Bridging social media via distant supervision

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Banerjee A, Basu S (2008) A social query model for decentralized search. In: Proceedings of the 2nd workshop on social network mining and analysiss, vol 124. ACM, New York

Dataset (2013) Twitter Dataset. https://github.com/gephi/gephi/wiki/Datasets. Accessed 13 Jan 2015

Duong Q, Goel S, Hofman J, Vassilvitskii S (2013) Sharding social networks. In: Proceedings of the sixth ACM international conference on Web search and data mining. ACM, pp 223–232

Hagberg AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in science conference (SciPy2008), Pasadena, CA, USA, pp 11–15

Horowitz D, Kamvar SD (2010) The anatomy of a large-scale social search engine. In: Proceedings of the 19th international conference on World wide web. ACM, pp 431–440

Jain R, Durresi A, Babic G (1999) Throughput fairness index: an explanation. Technical report, Department of CIS, The Ohio State University

Karagiannis T, Gkantsidis C, Narayanan D, Rowstron A (2010) Hermes: clustering users in large-scale e-mail services. In: Proceedings of the 1st ACM symposium on cloud computing. ACM, pp 89–100

Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Springer, New York, pp 85–103

Karypis G, Kumar V (1995) Metis—unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report

Karypis G, Kumar V (1998) Multilevelk-way partitioning scheme for irregular graphs. J Parallel Distrib Comput 48(1):96–129MathSciNetCrossRef

Leskovec J, Huttenlocher D, Kleinberg J (2010) Signed networks in social media. In: Proceedings of the SIGCHI conference on human factors in computing system. ACM, pp 1361–1370

Pujol JM, Erramilli V, Siganos G, Yang X, Laoutaris N, Chhabra P, Rodriguez P (2011) The little engine(s) that could: scaling online social networks. ACM SIGCOMM Comput Commun Rev 41(4):375–386

Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146–160MATHMathSciNetCrossRef

Tomita E, Tanaka A, Takahashi H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theor Comput Sci 363(1):28–42MATHMathSciNetCrossRef

Title: Sharding distributed social databases using social network analysis
Authors: Pranav Thulasiram Bhat
Rohit Varkey Thankachan
K. Chandrasekaran
Publication date: 01-12-2015
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2015
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-015-0274-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2015

On the network you keep: analyzing persons of interest using Cliqster

Interpreting communities based on the evolution of a dynamic attributed network

The unified model of social influence and its application in influence maximization

GLMLE: graph-limit enabled fast computation for fitting exponential random graph models to large social networks

Modeling influence diffusion to uncover influence centrality and community structure in social networks

A simulation method for social networks

Premium Partner