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

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

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

Content Provider	ACM Digital Library
Author	He, Kun Li, Yixuan Bindel, David Hopcroft, John E.
Abstract	Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms on mining communities have focused on the global structure, and often run in time functional to the size of the entire graph. Nowadays, as we often explore networks with billions of vertices and find communities of size hundreds, it is crucial to shift our attention from macroscopic structure to microscopic structure when dealing with large networks. A growing body of work has been adopting local expansion methods in order to identify the community from a few exemplary seed members. %Very few approaches can systematically demonstrate both high efficiency and effectiveness that significantly stands out amongst the divergent approaches in finding communities. In this paper, we propose a novel approach for finding overlapping communities called LEMON (Local Expansion via Minimum One Norm). Different from PageRank-like diffusion methods, LEMON finds the community by seeking a sparse vector in the span of the local spectra such that the seeds are in its support. We show that LEMON can achieve the highest detection accuracy among state-of-the-art proposals. The running time depends on the size of the community rather than that of the entire graph. The algorithm is easy to implement, and is highly parallelizable. Moreover, given that networks are not all similar in nature, a comprehensive analysis on how the local expansion approach is suited for uncovering communities in different networks is still lacking. We thoroughly evaluate our approach using both synthetic and real-world datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the quality and quantity of the seed set would affect the performance are provided.
Starting Page	658
Ending Page	668
Page Count	11
File Format	PDF
ISBN	9781450334693
DOI	10.1145/2736277.2741676
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-05-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Local spectral clustering Random walk Community detection Minimum one norm Seed set expansion
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