NDLI: Balanced label propagation for partitioning massive graphs

Please wait, while we are loading the content...

The virtual lab

Information-theoretic measures of influence based on content dynamics

Efficient and effective retrieval using selective pruning

Optimizing parallel algorithms for all pairs similarity search

Three findings regarding privacy online

Optimized interleaving for online retrieval evaluation

Mining the web to predict future events

Group sparse topical coding: from code to topic

Online multi-modal distance learning for scalable multimedia retrieval

Big data, lifelong machine learning and transfer learning

Balanced label propagation for partitioning massive graphs

GOP primary season on twitter: "popular" political sentiment in social media

Retweet or not?: personalized tweet re-ranking

Optimizing budget constrained spend in search advertising

Sponsored search auctions

Advanced graph mining for community evaluation in social networks and the web

Characterizing and curating conversation threads: expansion, focus, volume, re-entry

Document selection for tiered indexing in commerce search

Bursty subgraphs in social networks

Studying inter-national mobility through IP geolocation

TYPiMatch: type-specific unsupervised learning of keys and key values for heterogeneous web data integration

Unsupervised graph-based topic labelling using dbpedia

Towards Twitter context summarization with user influence models

Overlapping community detection at scale: a nonnegative matrix factorization approach

Characterizing and supporting cross-device search tasks

On the prediction of popularity of trends and hits for user generated videos

Anomaly, event, and fraud detection in large network datasets

Structure and dynamics of information pathways in online media

Quasi-succinct indices

Sharding social networks

From machu_picchu to "rafting the urubamba river": anticipating information needs via the entity-query graph

Robust query rewriting using anchor data

Estimating content concreteness for finding comprehensible documents

Exploiting social relations for sentiment analysis in microblogging

LaFT-tree: perceiving the expansion trace of one's circle of friends in online social networks

Learning to rank for spatiotemporal search

On the quest of discovering cultural trails in social media

Models and algorithms for social influence analysis

Cascade-based community detection

Identifying users' topical tasks in web search

Arrival and departure dynamics in social networks

Personalizing atypical web search sessions

Wiki3C: exploiting wikipedia for context-aware concept categorization

Translating related words to videos and back through latent topics

Connecting comments and tags: improved modeling of social tagging systems

A peek into the future: predicting the evolution of popularity in user generated content

Maguro, a system for indexing and searching over very large text collections

Towards web-scale structured web data extraction

Data-driven political science

Patent partner recommendation in enterprise social networks

Differences in search engine evaluations between query owners and non-owners

Expediting search trend detection via prediction of query counts

Crawling deep web entity pages

What's in a name?: an unsupervised approach to link users across communities

Co-factorization machines: modeling user interests and predicting individual decisions in Twitter

Online community detection in social sensing

Building user profiles to improve user experience in recommender systems

Exploring structure and content on the web: extraction and integration of the semi-structured web

Exploiting homophily effect for trust prediction

Optimizing top-k document retrieval strategies for block-max indexes

News recommendation via hypergraph learning: encapsulation of user behavior and news content

Using early view patterns to predict the popularity of youtube videos

Wikipedia entity expansion and attribute extraction from the web using semi-supervised learning

Distinguishing topical and social groups based on common identity and bond theory

Web usage mining for enhancing search-result delivery and helping users to find interesting web content

Temporal web dynamics and its application to information retrieval

Improving the sensitivity of online controlled experiments by utilizing pre-experiment data

Geo topic model: joint modeling of user's activity area and interests for location recommendation

Modeling the impact of lifestyle on health at scale

(big) usage data in web search

Playing by the rules: mining query associations to predict search performance

Latent factor models with additive and hierarchically-smoothed user preferences

Collective inference for network data with copula latent markov networks

Econometric analysis and digital marketing: how to measure the effectiveness of an ad

NCDawareRank: a novel ranking method that exploits the decomposable structure of the web

App recommendation: a contest between satisfaction and temptation

Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships

WSCD2013: workshop on web search click data 2013

Rank quantization

Threading machine generated email

Modeling dynamic behavior in large evolving graphs

3rd workshop on context-awareness in retrieval and recommendation

Time-sensitive web image ranking and retrieval via dynamic multi-task regression

Predicting content change on the web

On the streaming complexity of computing local clustering coefficients

Workshop on large-scale and distributed systems for information retrieval (LSDS-IR 2013)

Absence time and user engagement: evaluating ranking functions

Triplex transfer learning: exploiting both shared and distinct concepts for text classification

Learning query and document similarities from click-through bipartite graph with metadata

Workshop on semantic personalized information management (SPIM'13)

Reusing historical interaction data for faster online learning to rank for IR

Have you done anything like that?: predicting performance using inter-category reputation

Search and exploration of X-Rated information (SEXI 2013)

Pairwise ranking aggregation in a crowdsourced setting

Learning multiple-question decision trees for cold-start recommendation

Balanced label propagation for partitioning massive graphs

Content Provider	ACM Digital Library
Author	Backstrom, Lars Ugander, Johan
Abstract	Partitioning graphs at scale is a key challenge for any application that involves distributing a graph across disks, machines, or data centers. Graph partitioning is a very well studied problem with a rich literature, but existing algorithms typically can not scale to billions of edges, or can not provide guarantees about partition sizes. In this work we introduce an efficient algorithm, balanced label propagation, for precisely partitioning massive graphs while greedily maximizing edge locality, the number of edges that are assigned to the same shard of a partition. By combining the computational efficiency of label propagation --- where nodes are iteratively relabeled to the same 'label' as the plurality of their graph neighbors --- with the guarantees of constrained optimization --- guiding the propagation by a linear program constraining the partition sizes --- our algorithm makes it practically possible to partition graphs with billions of edges. Our algorithm is motivated by the challenge of performing graph predictions in a distributed system. Because this requires assigning each node in a graph to a physical machine with memory limitations, it is critically necessary to ensure the resulting partition shards do not overload any single machine. We evaluate our algorithm for its partitioning performance on the Facebook social graph, and also study its performance when partitioning Facebook's 'People You May Know' service (PYMK), the distributed system responsible for the feature extraction and ranking of the friends-of-friends of all active Facebook users. In a live deployment, we observed average query times and average network traffic levels that were 50.5% and 37.1% (respectively) when compared to the previous naive random sharding.
Starting Page	507
Ending Page	516
Page Count	10
File Format	PDF
ISBN	9781450318693
DOI	10.1145/2433396.2433461
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Graph clustering Graph partitioning Social networks Label propagation
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in