Statistical properties of sampled networks

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and online social networks (OSNs). Nowadays the massive size of some critical networks -- often stored in already overloaded relational databases -- effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propo...

Online social network services provide a platform for human social interactions. Nowadays, many kinds of online interactions generate large-scale social network data. Network analysis helps to mine knowledge and pattern from the relationship between actors inside the network. This approach is important to support predictions and the decision-making process in many real-world applications. The social network analysis methodology, which borrows approaches from graph theory prov...

This study introduces an algorithm that generates undirected graphs with three main characteristics of real-world networks: scale-freeness, short distances between nodes (small-world phenomenon), and large clustering coefficients. The main idea is to perform random walks across the network and, at each iteration, add special edges with a decreasing probability to link more distant nodes, following a specific probability distribution. A key advantage of our algorithm is its si...

The purpose of this paper is to assess the statistical characterization of weighted networks in terms of the generalization of the relevant parameters, namely average path length, degree distribution and clustering coefficient. Although the degree distribution and the average path length admit straightforward generalizations, for the clustering coefficient several different definitions have been proposed in the literature. We examined the different definitions and identified ...

Mapping the Internet generally consists in sampling the network from a limited set of sources by using "traceroute"-like probes. This methodology, akin to the merging of different spanning trees to a set of destinations, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. Here we explore these biases and provide a statistical analysis of their origin. We derive a ...

Most real world dynamic networks are evolved very fast with time. It is not feasible to collect the entire network at any given time to study its characteristics. This creates the need to propose local algorithms to study various properties of the network. In the present work, we estimate degree rank of a node without having the entire network. The proposed methods are based on the power law degree distribution characteristic or sampling techniques. The proposed methods are s...

Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network samp...

As large graph datasets become increasingly common across many fields, sampling is often needed to reduce the graphs into manageable sizes. This procedure raises critical questions about representativeness as no sample can capture the properties of the original graph perfectly, and different parts of the graph are not evenly affected by the loss. Recent work has shown that the distances from the non-sampled nodes to the sampled nodes can be a quantitative indicator of bias an...

The objective of this paper is to study the characteristics (geometric and otherwise) of very large attribute based undirected networks. Real-world networks are often very large and fast evolving. Their analysis and understanding present a great challenge. An Attribute based network is a graph in which the edges depend on certain properties of the vertices on which they are incident. In context of a social network, the existence of links between two individuals may depend on ...

We study the distribution of cycles of length h in large networks (of size N>>1) and find it to be an excellent ergodic estimator, even in the extreme inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, h* ~ N^a. Our results suggest that h* and the exponent a might usefully characterize broad families of networks. In addition to an exact counting of cycles in hierarchical nets, we present a Monte-Carlo sampling a...