NDLI: Estimating clustering coefficients and size of social networks via random walk

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

Real-time recommendation of diverse related articles

Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages

Hierarchical geographical modeling of user locations from social media posts

Distributed large-scale natural graph factorization

A CRM system for social media: challenges and experiences

Here's my cert, so trust me, maybe?: understanding TLS errors on the web

Towards a robust modeling of temporal interest change patterns for behavioral targeting

The anatomy of LDNS clusters: findings and implications for web content delivery

Steering user behavior with badges

Cascading tree sheets and recombinant HTML: better encapsulation and retargeting of web content

CopyCatch: stopping group attacks by spotting lockstep behavior in social networks

Inferring the demographics of search users: social data meets search queries

Strategyproof mechanisms for competitive influence in networks

Reactive crowdsourcing

On participation in group chats on Twitter

The role of web hosting providers in detecting compromised websites

Your browsing behavior for a big mac: economics of personal information online

Is this app safe for children?: a comparison study of maturity ratings on Android and iOS applications

Traveling the silk road: a measurement analysis of a large anonymous online marketplace

Group chats on Twitter

How to grow more pairs: suggesting review targets for comparison-friendly review ecosystems

A framework for benchmarking entity-annotation systems

A framework for learning web wrappers from the crowd

Lightweight server support for browser-based CSRF protection

Aggregating crowdsourced binary ratings

Optimal hashing schemes for entity matching

No country for old members: user lifecycle and linguistic change in online communities

Crowdsourced judgement elicitation with endogenous proficiency

Timespent based models for predicting user retention

Attributing authorship of revisioned content

ClausIE: clause-based open information extraction

Pick-a-crowd: tell me what you like, and i'll tell you what to do

Compact explanation of data fusion decisions

From query to question in one click: suggesting synthetic questions to searchers

Perception and understanding of social annotations in web search

AMIE: association rule mining under incomplete evidence in ontological knowledge bases

PrefixSolve: efficiently solving multi-source multi-destination path queries on RDF graphs by sharing suffix computations

When tolerance causes weakness: the case of injection-friendly browsers

Exploiting innocuous activity for correlating users across sites

The cost of annoying ads

Researcher homepage classification using unlabeled data

Google+ or Google-?: dissecting the evolution of the new OSN in its first year

Probabilistic group recommendation via information matching

WTF: the who to follow service at Twitter

Mining expertise and interests from social media

Measuring personalization of web search

Estimating clustering coefficients and size of social networks via random walk

Exploiting annotations for the rapid development of collaborative web applications

Web usage mining with semantic analysis

Organizational overlap on social networks and its applications

Space-efficient data structures for Top-k completion

Personalized recommendation via cross-domain triadic factorization

Unsupervised sentiment analysis with emotional signals

An analysis of socware cascades in online social networks

Measurement and analysis of child pornography trafficking on P2P networks

HeteroMF: recommendation in heterogeneous information networks using context dependent factor models

Interactive exploratory search for multi page search results

Spatio-temporal dynamics of online memes: a study of geo-tagged tweets

Accountable key infrastructure (AKI): a proposal for a public-key validation infrastructure

DIGTOBI: a recommendation system for Digg articles using probabilistic modeling

Understanding latency variations of black box services

Diversified recommendation on graphs: pitfalls, measures, and algorithms

What is the added value of negative links in online social networks?

Voices of victory: a computational focus group framework for tracking opinion shift in real time

Rethinking the web as a personal archive

Expressive languages for selecting groups from graph-structured data

Modeling/predicting the evolution trend of osn-based applications

SoCo: a social network aided context-aware recommender system

Using stranger as sensors: temporal and geo-sensitive question answering via social media

Imagen: runtime migration of browser sessions for javascript web applications

Gender swapping and user behaviors in online social games

Mining structural hole spanners through information diffusion in social networks

On the evolution of the internet economic ecosystem

Two years of short URLs internet measurement: security threats and countermeasures

Know your personalization: learning topic level personalization in online services

Saving, reusing, and remixing web video: using attitudes and practices to reveal social norms

From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews

The FLDA model for aspect-based opinion mining: addressing the cold start problem

Iolaus: securing online content rating systems

On cognition, emotion, and interaction aspects of search tasks with different search intentions

Ad impression forecasting for sponsored search

Measurement and modeling of eye-mouse behavior in the presence of nonlinear page layouts

Understanding and decreasing the network footprint of catch-up tv

Sorry, i don't speak SPARQL: translating SPARQL queries into natural language

Bitsquatting: exploiting bit-flips for fun, or profit?

One-class collaborative filtering with random graphs

Latent credibility analysis

Predicting group stability in online social networks

Predictive web automation assistant for people with vision impairments

Mining collective intelligence in diverse groups

Trade area analysis using user generated mobile location data

Psychological maps 2.0: a web engagement enterprise starting in London

Towards realistic team formation in social networks based on densest subgraphs

Efficient community detection in large networks using content and links

Learning joint query interpretation and response ranking

A model for green design of online news media services

Potential networks, contagious communities, and understanding social network structure

Do social explanations work?: studying and modeling the effects of social explanations in recommender systems

Question answering on interlinked data

Pricing mechanisms for crowdsourcing markets

Truthful incentives in crowdsourcing tasks using regret minimization mechanisms

A predictive model for advertiser value-per-click in sponsored search

I know the shortened URLs you clicked on Twitter: inference attack using public click analytics and Twitter metadata

Exploring and exploiting user search behavior on mobile and tablet devices to improve search relevance

Evaluating and predicting user engagement change with degraded search relevance

Data-Fu: a language and an interpreter for interaction with read/write linked data

NIFTY: a system for large scale information flow tracking and clustering

When relevance is not enough: promoting diversity and freshness in personalized question recommendation

Mining acronym expansions and their meanings using query click log

Groundhog day: near-duplicate detection on Twitter

Uncovering locally characterizing regions within geotagged data

Spectral analysis of communication networks using Dirichlet eigenvalues

Subgraph frequencies: mapping the empirical and extremal geography of large graph collections

The self-feeding process: a unifying model for communication dynamics in the web

Google+Ripples: a native visualization of information flow

Whom to mention: expand the diffusion of tweets by @ recommendation on micro-blogging systems

Wisdom in the social crowd: an analysis of quora

Learning to extract cross-session search tasks

Content-aware click modeling

Is it time for a career switch?

From cookies to cooks: insights on dietary patterns via analysis of web usage logs

Enhancing personalized search by mining and modeling task behavior

Inferring dependency constraints on parameters for web services

Predicting advertiser bidding behaviors in sponsored search by rationality modeling

A biterm topic model for short texts

Unified entity search in social media community

MATRI: a multi-aspect and transitive trust inference model

Predicting positive and negative links in signed social networks by transfer learning

Sparse online topic models

TopRec: domain-specific recommendation through community topic mining in social network

Localized matrix factorization for recommendation based on matrix block diagonal forms

Predicting purchase behaviors from social media

Anatomy of a web-scale resale market: a data mining approach

Questions about questions: an empirical analysis of information needs on Twitter

Which vertical search engines are relevant?

Making the most of your triple store: query answering in OWL 2 using an RL reasoner

Security implications of password discretization for click-based graphical passwords

Estimating clustering coefficients and size of social networks via random walk

Content Provider	ACM Digital Library
Author	Hardiman, Stephen J. Katzir, Liran
Abstract	Online social networks have become a major force in today's society and economy. The largest of today's social networks may have hundreds of millions to more than a billion users. Such networks are too large to be downloaded or stored locally, even if terms of use and privacy policies were to permit doing so. This limitation complicates even simple computational tasks. One such task is computing the clustering coefficient of a network. Another task is to compute the network size (number of registered users) or a subpopulation size. The clustering coefficient, a classic measure of network connectivity, comes in two flavors, global and network average. In this work, we provide efficient algorithms for estimating these measures which (1) assume no prior knowledge about the network; and (2) access the network using only the publicly available interface. More precisely, this work provides three new estimation algorithms (a) the first external access algorithm for estimating the global clustering coefficient; (b) an external access algorithm that improves on the accuracy of previous network average clustering coefficient estimation algorithms; and (c) an improved external access network size estimation algorithm. The main insight offered by this work is that only a relatively small number of public interface calls are required to allow our algorithms to achieve a high accuracy estimation. Our approach is to view a social network as an undirected graph and use the public interface to retrieve a random walk. To estimate the clustering coefficient, the connectivity of each node in the random walk sequence is tested in turn. We show that the error of this estimation drops exponentially in the number of random walk steps. Another insight of this work is the fact that, although the proposed algorithms can be used to estimate the clustering coefficient of any undirected graph, they are particularly efficient on social network-like graphs. To improve the network size prior-art estimation algorithms, we count node collision one step before they actually occur. In our experiments we validate our algorithms on several publicly available social network datasets. Our results validate the theoretical claims and demonstrate the effectiveness of our algorithms.
Starting Page	539
Ending Page	550
Page Count	12
File Format	PDF
ISBN	9781450320351
DOI	10.1145/2488388.2488436
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-05-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Estimation Social network Clustering coefficient Sampling
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