eCite Digital Repository

Resampling-based gap analysis for detecting nodes with high centrality on large social network


Ohara, K and Saito, K and Kimura, M and Motoda, H, Resampling-based gap analysis for detecting nodes with high centrality on large social network, Proceedings of the Advances in Knowledge Discovery and Data Mining 19th Pacific-Asia Conference (PAKDD 2015), 19-22 May 2015, Ho Chi Minh City, Vietnam, pp. 135-147. ISBN 978-3-319-18037-3 (2015) [Refereed Conference Paper]

Not available

Copyright Statement

Copyright 2015 Springer International Publishing

Official URL: 11

DOI: doi:10.1007/978-3-319-18038-0_11


We address a problem of identifying nodes having a high centrality value in a large social network based on its approximation derived only from nodes sampled from the network. More specifically, we detect gaps between nodes with a given confidence level, assuming that we can say a gap exists between two adjacent nodes ordered in descending order of approximations of true centrality values if it can divide the ordered list of nodes into two groups so that any node in one group has a higher centrality value than any one in another group with a given confidence level. To this end, we incorporate confidence intervals of true centrality values, and apply the resampling-based framework to estimate the intervals as accurately as possible. Furthermore, we devise an algorithm that can efficiently detect gaps by making only two passes through the nodes, and empirically show, using three real world social networks, that the proposed method can successfully detect more gaps, compared to the one adopting a standard error estimation framework, using the same node coverage ratio, and that the resulting gaps enable us to correctly identify a set of nodes having a high centrality value.

Item Details

Item Type:Refereed Conference Paper
Keywords:gap analysis, error estimation, resampling, node centrality
Research Division:Information and Computing Sciences
Research Group:Distributed computing and systems software
Research Field:Networking and communications
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the information and computing sciences
UTAS Author:Motoda, H (Dr Hiroshi Motoda)
ID Code:109270
Year Published:2015
Web of Science® Times Cited:1
Deposited By:Information and Communication Technology
Deposited On:2016-06-06
Last Modified:2018-01-17

Repository Staff Only: item control page