NDLI: QUBE: a quick algorithm for updating betweenness centrality

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

Build your own music recommender by modeling internet radio streams

How far can client-only solutions go for mobile browser speed?

Understanding and combating link farming in the twitter social network

Risk-aware revenue maximization in display advertising

Compressed data structures for annotated web search

TailGate: handling long-tail content with a little help from friends

Semi-supervised correction of biased comment ratings

Musubi: disintermediated interactive social feeds for mobile devices

YouTube around the world: geographic popularity of videos

Factorizing YAGO: scalable machine learning for linked data

Investigating the distribution of password choices

Using content and interactions for discovering communities in social networks

On revenue in the generalized second price auction

Structured query suggestion for specialization and parallel movement: effect on search behaviors

Multi-objective ranking of comments on web

LINDEN: linking named entities with knowledge base via semantic knowledge

A flexible generative model for preference aggregation

Information transfer in social media

Implementing optimal outcomes in social computing: a game-theoretic approach

Beyond dwell time: estimating document relevance from cursor movements and other post-click searcher behavior

Modeling and predicting behavioral dynamics on the web

Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard

Practical end-to-end web content integrity

Actions speak as loud as words: predicting relationships from social behavior data

Targeted disambiguation of ad-hoc, homogeneous sets of named entities

Mining photo-sharing websites to study ecological phenomena

Declarative platform for data sourcing games

On the analysis of cascading style sheets

Online team formation in social networks

Micropinion generation: an unsupervised approach to generating ultra-concise summaries of opinions

Trains of thought: generating information maps

A unified approach to learning task-specific bit vector representations for fast nearest neighbor search

Towards network-aware service composition in the cloud

Max algorithms in crowdsourcing environments

Vertex collocation profiles: subgraph counting for link analysis and prediction

A dual-mode user interface for accessing 3D content on the world wide web

Using control theory for stable and efficient recommender systems

Who killed my battery?: analyzing mobile browser energy consumption

Analyzing spammers' social networks for fun and profit: a case study of cyber criminal ecosystem on twitter

Targeting converters for new campaigns through factor models

The SemSets model for ad-hoc semantic list search

DOHA: scalable real-time web applications through adaptive concurrent execution

Spotting fake reviewer groups in consumer reviews

Economics of BitTorrent communities

Dynamical classes of collective attention in twitter

Semantic navigation on the web of data: specification of routes, web fragments and actions

Is this app safe?: a large scale study on application permissions and risk signals

Community detection in incomplete information networks

Handling forecast errors while bidding for display advertising

Partitioned multi-indexing: bringing order to social search

Care to comment?: recommendations for commenting on news stories

Cross-lingual knowledge linking across wiki knowledge bases

Evaluating the effectiveness of search task trails

The role of social networks in information diffusion

Lattice games and the economics of aggregators

Joint relevance and freshness learning from clickthroughs for news search

Are web users really Markovian?

Template-based question answering over RDF data

Online modeling of proactive moderation system for auction fraud detection

Echoes of power: language effects and power differences in social interaction

Collective context-aware topic models for entity disambiguation

Learning from the past: answering new questions with past answers

Information integration over time in unreliable and uncertain environments

Extracting client-side web application code

Understanding task-driven information flow in collaborative networks

Mr. LDA: a flexible large scale topic modeling package using variational inference in MapReduce

Learning causality for news events prediction

Lightweight automatic face annotation in media pages

Towards robust service compositions in the context of functionally diverse services

Crowdsourcing with endogenous entry

Framework and algorithms for network bucket testing

Exploiting single-user web applications for shared editing: a generic transformation approach

An exploration of improving collaborative recommender systems via user-item subgroups

Periodic transfers in mobile applications: network-wide origin, impact, and optimization

Branded with a scarlet "C": cheaters in a gaming social network

How effective is targeted advertising?

Heterogeneous web data search using relevance-based on the fly data integration

Surviving a search engine overload

Estimating the prevalence of deception in online review communities

A habit mining approach for discovering similar mobile users

We know what @you #tag: does the dual role affect hashtag adoption?

Understanding web images by object relation network

SessionJuggler: secure web login from an untrusted terminal using session hijacking

QUBE: a quick algorithm for updating betweenness centrality

Optimizing budget allocation among channels and influencers

Unsupervised extraction of template structure in web search queries

Leveraging user comments for aesthetic aware image search reranking

ZenCrowd: leveraging probabilistic reasoning and crowdsourcing techniques for large-scale entity linking

Evaluation with informational and navigational intents

Recommendations to boost content spread in social networks

Strategic formation of credit networks

Active objects: actions for entity-centric search

Human wayfinding in information networks

On directly mapping relational databases to RDF and OWL

Serf and turf: crowdturfing for fun and profit

Bimodal invitation-navigation fair bets model for authority identification in a social network

Document hierarchies from text and links

Discovering geographical topics in the twitter stream

SAFE extensibility of data-driven web applications

OPAL: automated form understanding for the deep web

New objective functions for social collaborative filtering

Your two weeks of fame and your grandmother's

Distributed graph pattern matching

CloudGenius: decision support for web server cloud migration

Answering search queries with CrowdSearcher

Winner takes all: competing viruses or ideas on fair-play networks

"It's simply integral to what I do": enquiries into how the web is weaved into everyday life

QUBE: a quick algorithm for updating betweenness centrality

Content Provider	ACM Digital Library
Author	Lee, Min-Joong Chung, Chin-Wan Lee, Jungmin Choi, Ryan Hyun Park, Jaimie Yejean
Abstract	The betweenness centrality of a vertex in a graph is a measure for the participation of the vertex in the shortest paths in the graph. The Betweenness centrality is widely used in network analyses. Especially in a social network, the recursive computation of the betweenness centralities of vertices is performed for the community detection and finding the influential user in the network. Since a social network graph is frequently updated, it is necessary to update the betweenness centrality efficiently. When a graph is changed, the betweenness centralities of all the vertices should be recomputed from scratch using all the vertices in the graph. To the best of our knowledge, this is the first work that proposes an efficient algorithm which handles the update of the betweenness centralities of vertices in a graph. In this paper, we propose a method that efficiently reduces the search space by finding a candidate set of vertices whose betweenness centralities can be updated and computes their betweenness centeralities using candidate vertices only. As the cost of calculating the betweenness centrality mainly depends on the number of vertices to be considered, the proposed algorithm significantly reduces the cost of calculation. The proposed algorithm allows the transformation of an existing algorithm which does not consider the graph update. Experimental results on large real datasets show that the proposed algorithm speeds up the existing algorithm 2 to 2418 times depending on the dataset.
Starting Page	351
Ending Page	360
Page Count	10
File Format	PDF
ISBN	9781450312295
DOI	10.1145/2187836.2187884
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-04-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Update algorithm Betweenness centrality
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