NDLI: Efficient Densest Subgraph Computation in Evolving Graphs

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

Optimizing Display Advertising in Online Social Networks

SCULPT: A Schema Language for Tabular Data on the Web

Frankenplace: Interactive Thematic Mapping for Ad Hoc Exploratory Search

The Web as a Jungle: Non-Linear Dynamical Systems for Co-evolving Online Activities

Towards Reconciling SPARQL and Certain Answers

Spanning Edge Centrality: Large-scale Computation and Applications

Donor Retention in Online Crowdfunding Communities: A Case Study of DonorsChoose.org

No Escape From Reality: Security and Privacy of Augmented Reality Browsers

Budget-Constrained Item Cold-Start Handling in Collaborative Filtering Recommenders via Optimal Design

Discovering Meta-Paths in Large Heterogeneous Information Networks

Improved Theoretical and Practical Guarantees for Chromatic Correlation Clustering

From "Selena Gomez" to "Marlon Brando": Understanding Explorative Entity Search

Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily

Children Seen But Not Heard: When Parents Compromise Children's Online Privacy

Recommendation Subgraphs for Web Discovery

TrueView: Harnessing the Power of Multiple Review Sites

Is Sniping A Problem For Online Auction Markets?

QUOTUS: The Structure of Political Media Coverage as Revealed by Quoting Patterns

Essential Web Pages Are Easy to Find

Energy and Performance of Smartphone Radio Bundling in Outdoor Environments

Design and Analysis of Benchmarking Experiments for Distributed Internet Services

PriVaricator: Deceiving Fingerprinters with Little White Lies

ACCAMS: Additive Co-Clustering to Approximate Matrices Succinctly

Diagnoses, Decisions, and Outcomes: Web Search as Decision Support for Cancer

Who, What, When, and Where: Multi-Dimensional Collaborative Recommendations Using Tensor Factorization on Sparse User-Generated Data

PocketTrend: Timely Identification and Delivery of Trending Search Content to Mobile Users

Secrets, Lies, and Account Recovery: Lessons from the Use of Personal Knowledge Questions at Google

Overcoming Relational Learning Biases to Accurately Predict Preferences in Large Scale Networks

Supporting Ethical Web Research: A New Research Ethics Review

Deriving an Emergent Relational Schema from RDF Data

Sequential Hypothesis Tests for Adaptive Locality Sensitive Hashing

The Digital Life of Walkable Streets

Opinion Spam Detection in Web Forum: A Real Case Study

Beyond Models: Forecasting Complex Network Processes Directly from Data

Summarizing Entity Descriptions for Effective and Efficient Human-centered Entity Linking

Weakly Supervised Extraction of Computer Security Events from Twitter

Semantic Tagging of Mathematical Expressions

Groupsourcing: Team Competition Designs for Crowdsourcing

Collaborative Ranking with a Push at the Top

Authentication Melee: A Usability Analysis of Seven Web Authentication Systems

Parallel Streaming Signature EM-tree: A Clustering Algorithm for Web Scale Applications

Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions

Network-based Origin Confusion Attacks against HTTPS Virtual Hosting

Bringing CUPID Indoor Positioning System to Practice

The Dynamics of Micro-Task Crowdsourcing: The Case of Amazon MTurk

Early Detection of Spam Mobile Apps

Hierarchical Neural Language Models for Joint Representation of Streaming Documents and their Content

N-gram IDF: A Global Term Weighting Scheme Based on Information Distance

Future User Engagement Prediction and Its Application to Improve the Sensitivity of Online Experiments

Query Suggestion and Data Fusion in Contextual Disambiguation

Enriching Structured Knowledge with Open Information

Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment

A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems

Language Understanding in the Wild: Combining Crowdsourcing and Machine Learning

Cookies That Give You Away: The Surveillance Implications of Web Tracking

HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web

Efficient Densest Subgraph Computation in Evolving Graphs

Exploiting Collective Hidden Structures in Webpage Titles for Open Domain Entity Extraction

A Practical Framework for Privacy-Preserving Data Analytics

ROCKER: A Refinement Operator for Key Discovery

Compressed Indexes for String Searching in Labeled Graphs

Random Walk TripleRush: Asynchronous Graph Querying and Sampling

Improving Paid Microtasks through Gamification and Adaptive Furtherance Incentives

Open Domain Question Answering via Semantic Enrichment

Tagging Personal Photos with Transfer Deep Learning

All Who Wander: On the Prevalence and Characteristics of Multi-community Engagement

MobInsight: On Improving The Performance of Mobile Apps in Cellular Networks

LINE: Large-scale Information Network Embedding

Rethinking Security of Web-Based System Applications

Leveraging Pattern Semantics for Extracting Entities in Enterprises

Cardinal Contests

Density-friendly Graph Decomposition

Accessible On-Line Floor Plans

Crowd Fraud Detection in Internet Advertising

Network A/B Testing: From Sampling to Estimation

Provably Fast Inference of Latent Features from Networks: with Applications to Learning Social Circles and Multilabel Classification

User Session Identification Based on Strong Regularities in Inter-activity Time

The K-clique Densest Subgraph Problem

Incentivizing High Quality Crowdwork

GERBIL: General Entity Annotator Benchmarking Framework

Skolemising Blank Nodes while Preserving Isomorphism

An Optimization Framework for Weighting Implicit Relevance Labels for Personalized Web Search

Scalable Methods for Adaptively Seeding a Social Network

A First Look at Tribal Web Traffic

User Review Sites as a Resource for Large-Scale Sociolinguistic Studies

A Weighted Correlation Index for Rankings with Ties

When Does Improved Targeting Increase Revenue?

Gathering Additional Feedback on Search Results by Multi-Armed Bandits with Respect to Production Ranking

Social Status and Badge Design

The E-Commerce Market for "Lemons": Identification and Analysis of Websites Selling Counterfeit Goods

Mapping Temporal Horizons: Analysis of Collective Future and Past related Attention in Twitter

Concept Expansion Using Web Tables

Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts

User Latent Preference Model for Better Downside Management in Recommender Systems

Automatic Online Evaluation of Intelligent Assistants

The Role of Data Cap in Optimal Two-part Network Pricing

Incorporating Social Context and Domain Knowledge for Entity Recognition

Tweeting Cameras for Event Detection

Querying Web-Scale Information Networks Through Bounding Matching Scores

Mining Missing Hyperlinks from Human Navigation Traces: A Case Study of Wikipedia

LN-Annote: An Alternative Approach to Information Extraction from Emails using Locally-Customized Named-Entity Recognition

Semantic Annotation of Mobility Data using Social Media

Describing and Understanding Neighborhood Characteristics through Online Social Media

Automatic Web Content Extraction by Combination of Learning and Grouping

Active Learning for Multi-relational Data Construction

Executing Provenance-Enabled Queries over Web Data

The Social World of Content Abusers in Community Question Answering

Understanding Malvertising Through Ad-Injecting Browser Extensions

The Lifecycles of Apps in a Social Ecosystem

E-commerce Reputation Manipulation: The Emergence of Reputation-Escalation-as-a-Service

Getting More for Less: Optimized Crowdsourcing with Dynamic Tasks and Goals

Effective Techniques for Message Reduction and Load Balancing in Distributed Graph Computation

Evolution of Conversations in the Age of Email Overload

Tackling the Achilles Heel of Social Networks: Influence Propagation based Language Model Smoothing

Events and Controversies: Influences of a Shocking News Event on Information Seeking

A Game Theoretic Model for the Formation of Navigable Small-World Networks

Statistically Significant Detection of Linguistic Change

A Scalable Asynchronous Distributed Algorithm for Topic Modeling

Replacing the Irreplaceable: Fast Algorithms for Team Member Recommendation

LightLDA: Big Topic Models on Modest Computer Clusters

Robust Group Linkage

A Novelty-Seeking based Dining Recommender System

Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach

Daily-Aware Personalized Recommendation based on Feature-Level Time Series Analysis

Scalable Parallel EM Algorithms for Latent Dirichlet Allocation in Multi-Core Systems

Automatic Detection of Information Leakage Vulnerabilities in Browser Extensions

Grading the Graders: Motivating Peer Graders in a MOOC

Enquiring Minds: Early Detection of Rumors in Social Media from Enquiry Posts

Measurement and Analysis of Mobile Web Cache Performance

Improving User Topic Interest Profiles by Behavior Factorization

Predicting Pinterest: Automating a Distributed Human Computation

Efficient Densest Subgraph Computation in Evolving Graphs

Content Provider	ACM Digital Library
Author	Epasto, Alessandro Sozio, Mauro Lattanzi, Silvio
Abstract	Densest subgraph computation has emerged as an important primitive in a wide range of data analysis tasks such as community and event detection. Social media such as Facebook and Twitter are highly dynamic with new friendship links and tweets being generated incessantly, calling for efficient algorithms that can handle very large and highly dynamic input data. While either scalable or dynamic algorithms for finding densest subgraphs have been proposed, a viable and satisfactory solution for addressing both the dynamic aspect of the input data and its large size is still missing. We study the densest subgraph problem in the the dynamic graph model, for which we present the first scalable algorithm with provable guarantees. In our model, edges are added adversarially while they are removed uniformly at random from the current graph. We show that at any point in time we are able to maintain a 2(1+ε)-approximation of a current densest subgraph, while requiring O(polylog(n+r)) amortized cost per update (with high probability), where r is the total number of update operations executed and n is the maximum number of nodes in the graph. In contrast, a naive algorithm that recomputes a dense subgraph every time the graph changes requires Omega(m) work per update, where m is the number of edges in the current graph. Our theoretical analysis is complemented with an extensive experimental evaluation on large real-world graphs showing that (approximate) densest subgraphs can be maintained efficiently within hundred of microseconds per update.
Starting Page	300
Ending Page	310
Page Count	11
File Format	PDF
ISBN	9781450334693
DOI	10.1145/2736277.2741638
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-05-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Densest subgraph Approximation algorithm Dynamic graph
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