DocumentCode :
2194973
Title :
Estimating Centrality Statistics for Complete and Sampled Networks: Some Approaches and Complications
Author :
Ju-Sung Lee ; Pfeffer, Juergen
Author_Institution :
Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, CA, USA
fYear :
2015
fDate :
5-8 Jan. 2015
Firstpage :
1686
Lastpage :
1695
Abstract :
The study of large, "big data" networks is becoming increasingly common and relevant to our understanding of human systems. Many of the studied networks are drawn from social media and other Web-based sources. As such, in-depth analysis of these dynamic structures e.g. In the context of cyber security, remains especially challenging. Due to the time and resources incurred in computing network measures for large networks, it is practical to approximate these whenever possible. We present some approximation techniques exploiting any tractable relationship between the measures and network characteristics such as size and density. We find there exist distinct functional relationships between network statistics of complex "slow" measures and "fast" measures, such as the linkage between betweenness centrality and network density. We also track how these relationships scale with network size. Specifically, we explore the efficacy of both linear modeling (i.e., Correlations and least squares regression) and non-linear modeling in estimating the network measures of interest. We find that sparse, but not severely sparse, networks which admit sufficient entropy incur the most variance in the network statistics and, hence, more error in the estimation. We review our approaches with three prominent network topologies: random (aka Erdos-Renyi), Watts-Strogatz small-world, and scale-free networks. Finally, we assess how well the estimation approaches perform for sub-sampled networks.
Keywords :
Big Data; computational complexity; network theory (graphs); small-world networks; statistical analysis; Big Data networks; Erdos-Renyi network; Watts-Strogatz small-world network; Web-based sources; approximation techniques; centrality statistics estimation; complete networks; complex-fast-measures; complex-slow-measures; correlation analysis; cybersecurity; dynamic structure analysis; entropy; functional relationships; human systems; large-network measures; least squares regression; linear modeling; network centrality; network characteristics; network density; network size; network topologies; nonlinear modeling; random network; sampled networks; scale-free networks; social media; subsampled networks; Correlation; Density measurement; Erbium; Estimation; Network topology; Topology; Velocity measurement; graph typology; network analysis; sampling error;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
System Sciences (HICSS), 2015 48th Hawaii International Conference on
Conference_Location :
Kauai, HI
ISSN :
1530-1605
Type :
conf
DOI :
10.1109/HICSS.2015.203
Filename :
7070013
Link To Document :
بازگشت