We derive properties of latent variable models for networks, a broad class of models that includes the widely used latent position models. We characterize several features of interest, with particular focus on the degree distribution, clustering coefficient, average path length, and degree correlations. We introduce the Gaussian latent position model, and derive analytic expressions and asymptotic approximations for its network properties. We pay particular attention to one special case, the Gaussian latent position model with random effects, and show that it can represent the heavy-tailed degree distributions, positive asymptotic clustering coefficients, and small-world behaviors that often occur in observed social networks. Finally, we illustrate the ability of the models to capture important features of real networks through several well-known datasets.

We sketch the history of spectral ranking—a general umbrella name for techniques that apply the theory of linear maps (in particular, eigenvalues and eigenvectors) to matrices that do not represent geometric transformations, but rather some kind of relationship between entities. Albeit recently made famous by the ample press coverage of Google's PageRank algorithm, spectral ranking was devised more than 60 years ago, almost exactly in the same terms, and has been studied in psychology, social sciences, bibliometrics, economy, and choice theory. We describe the contribution given by previous scholars in precise and modern mathematical terms: Along the way, we show how to express in a general way damped rankings, such as Katz's index, as dominant eigenvectors of perturbed matrices, and then use results on the Drazin inverse to go back to the dominant eigenvectors by a limit process. The result suggests a regularized definition of spectral ranking that yields for a general matrix a unique vector depending on a boundary condition.

In this paper, we attempt to investigate the attack tolerance of human mobility networks where the mobility is restricted to some extent, for instance, in a hospital, one is not allowed to access all locations. Similar situations also arise in schools. In such a network, we will show that people need to rely upon some intermediate agents, popularly known as the brokers to disseminate information. In order to establish this fact, we have followed the approach of attack in a network which in turn helps to identify important nodes in the network in order to maintain the overall connectivity. In this direction, we have proposed, a new temporal metric, brokerage frequency which significantly outperforms all other state-of-the-art attack strategies reported in Trajanovski et al. (2012), Sur et al. (2015).

Network centrality has been addressed for more than 30 years; however, few studies provided statistical tests for verifying this network characteristic. By applying the idea of focus test in spatial analysis, we propose a statistical method to test the centrality of a network. We consider not only the degree of node, but also give weights on other nodes with different lengths of the shortest paths, which are called “distances” in networks. According to the density of distance based on the hidden variable model and the property of the multinomial distribution, a test statistic called “focus centrality” is provided to evaluate a network centrality. Besides the theoretical construction, we verify that the proposed method is feasible and effective in the simulation studies. Further, two empirical network data are studied as demonstrations.

We confirm a conjecture by Everett et al. (2004) regarding the problem of maximizing closeness centralization in two-mode data, where the number of data of each type is fixed. Intuitively, our result states that among all networks obtainable via two-mode data, the largest closeness is achieved by simply locally maximizing the closeness of a node. Mathematically, our study concerns bipartite graphs with fixed size bipartitions, and we show that the extremal configuration is a rooted tree of depth 2, where neighbors of the root have an equal or almost equal number of children.

We consider a network of interacting individuals, whose actions or transitions are determined by the states (behavior) of their neighbors as well as their own personal decisions. Specifically, we develop a model according to two simple decision-making rules that can describe the growth of the user population of a newly launched product or service. We analyze 22 sets of real-world historical growth data of a variety of products and services, and show that they all follow the growth equation. The numerical procedure for finding the model parameters allows the market size, and the relative effectiveness of customer service and promotional efforts to be estimated from the available historical growth data. We study the growth profiles of products and find that for a product or service to reach a mature stage within a reasonably short time in its user growth profile, the user growth rate corresponding to influenced transitions must exceed a certain threshold. Furthermore, results show that individuals in the group of celebrities having numerous friends become users of a new product or service at a much faster rate than those connected to ordinary individuals having fewer friends.

We introduce NetworKit, an open-source software package for analyzing the structure of large complex networks. Appropriate algorithmic solutions are required to handle increasingly common large graph data sets containing up to billions of connections. We describe the methodology applied to develop scalable solutions to network analysis problems, including techniques like parallelization, heuristics for computationally expensive problems, efficient data structures, and modular software architecture. Our goal for the software is to package results of our algorithm engineering efforts and put them into the hands of domain experts. NetworKit is implemented as a hybrid combining the kernels written in C++ with a Python frontend, enabling integration into the Python ecosystem of tested tools for data analysis and scientific computing. The package provides a wide range of functionality (including common and novel analytics algorithms and graph generators) and does so via a convenient interface. In an experimental comparison with related software, NetworKit shows the best performance on a range of typical analysis tasks.