Abstract

The dynamics of collaboration networks of firms follow a life-cycle of growth and decline. That does not imply they also become less resilient. Instead, declining collaboration networks may still have the ability to mitigate shocks from firms leaving, and to recover from these losses by adapting to new partners. To demonstrate this, we analyze 21.500 R&D collaborations of 14.500 firms in six different industrial sectors over 25 years. We calculate time-dependent probabilities of firms leaving the network and simulate drop-out cascades, to determine the expected dynamics of decline. We then show that deviations from these expectations result from the adaptivity of the network, which mitigates the decline. These deviations can be used as a measure of network resilience.

Abstract

We propose a novel sequence prediction method for sequential data capturing node traversals in graphs. Our method builds on a statistical modelling framework that combines multiple higher-order network models into a single multi-order model. We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. Our framework facilitates both next-element and full sequence prediction given a sequence-prefix of any length. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. The results show that our method out-performs state-of-the-art algorithms for next-element prediction. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.

Abstract

We investigate a multi-agent model of firms in a Research & Development (R&D) network. Each firm is characterized by its knowledge stock xi(t), which follows a non-linear dynamics. xi(t) grows with the input from other firms, i.e., by knowledge transfer, and decays otherwise. However, maintaining the interactions that increase knowledge stock is costly for all partners involved. Because of this, firms leave the network whenever their expected knowledge growth is not realized. This, in turn, may cause other firms also to leave the network. The paper discusses two bottom-up intervention scenarios to prevent, reduce, or delay such cascades of firms leaving. The first one is based on the formalism of network controllability, in which driver nodes are identified and subsequently incentivized, by reducing their costs. The second one combines node interventions and network interventions. It proposes the controlled removal of a single firm and the random replacement of firms leaving. This allows to generate small cascades, which prevents the occurrence of large cascades. We find that both approaches successfully mitigate cascades and thus improve the resilience of the R&D network.

Abstract

The unsupervised detection of anomalies in time series data has important applications in user behavioral modeling, fraud detection, and cybersecurity. Anomaly detection has, in fact, been extensively studied in categorical sequences. However, we often have access to time series data that represent paths through networks. Examples include transaction sequences in financial networks, click streams of users in networks of cross-referenced documents, or travel itineraries in transportation networks. To reliably detect anomalies, we must account for the fact that such data contain a large number of independent observations of paths constrained by a graph topology. Moreover, the heterogeneity of real systems rules out frequency-based anomaly detection techniques, which do not account for highly skewed edge and degree statistics. To address this problem, we introduce HYPA, a novel framework for the unsupervised detection of anomalies in large corpora of variable-length temporal paths in a graph. HYPA provides an efficient analytical method to detect paths with anomalous frequencies that result from nodes being traversed in unexpected chronological order.

Abstract

Online social networks (OSN) are prime examples of socio-technical systems in which individuals interact via a technical platform. OSN are very volatile because users enter and exit and frequently change their interactions. This makes the robustness of such systems difficult to measure and to control. To quantify robustness, we propose a coreness value obtained from the directed interaction network. We study the emergence of large drop-out cascades of users leaving the OSN by means of an agent-based model. For agents, we define a utility function that depends on their relative reputation and their costs for interactions. The decision of agents to leave the OSN depends on this utility. Our aim is to prevent drop-out cascades by influencing specific agents with low utility. We identify strategies to control agents in the core and the periphery of the OSN such that drop-out cascades are significantly reduced, and the robustness of the OSN is increased.

Abstract

We provide a novel family of generative block-models for random graphs that naturally incorporates degree distributions: the block-constrained configuration model. Block-constrained configuration models build on the generalized hypergeometric ensemble of random graphs and extend the well-known configuration model by enforcing block-constraints on the edge-generating process. The resulting models are practical to fit even to large networks. These models provide a new, flexible tool for the study of community structure and for network science in general, where modeling networks with heterogeneous degree distributions is of central importance.

Abstract

We consider a multi-layer network with two layers, $\_1\$, $\_2\$. Their intra-layer topology shows a scale-free degree distribution and a core-periphery structure. A nested structure describes the inter-layer topology, i.e., some nodes from $\_1\$, the generalists, have many links to nodes in $\_2\$, specialists only have a few. This structure is verified by analyzing two empirical networks from ecology and economics. To probe the robustness of the multi-layer network, we remove nodes from $\_1\$ with their inter-and intra-layer links and measure the impact on the size of the largest connected component, $F_2\$, in $\_2\$, which we take as a robustness measure. We test different attack scenarios by preferably removing peripheral or core nodes. We also vary the intra-layer coupling between generalists and specialists, to study their impact on the robustness of the multi-layer network. We find that some combinations of attack scenario and intra-layer coupling lead to very low robustness values, whereas others demonstrate high robustness of the multi-layer network because of the intra-layer links. Our results shed new light on the robustness of bipartite networks, which consider only inter-layer, but no intra-layer links.

Abstract

This paper proposes a Gaussian process-based self-organizing incremental neural network (GPINN) to address the density estimation problem of online unsupervised learning. First, we adopt Gaussian process models with adaptive kernels that map the distribution of the neighbors of each node to its link relationship. Second, combining GPINN and kernel density estimation, we derive the bandwidth matrix updating rule for adapting to the generated network. We theoretically analyze the advantages of the proposed approach in determining threshold regions over using distance measures. The experimental results on both synthetic data sets and real-world data sets show that our method achieves remarkable improvement in density estimation accuracy for large noisy data.

Abstract

We quantify a social organization's potentiality, that is its ability to attain different configurations. The organization is represented as a network in which nodes correspond to individuals and (multi-)edges to their multiple interactions. Attainable configurations are treated as realizations from a network ensemble. To encode interaction preferences between individuals, we choose the generalized hypergeometric ensemble of random graphs, which is described by a closed-form probability distribution. From this distribution we calculate Shannon entropy as a measure of potentiality. This allows us to compare different organizations as well different stages in the development of a given organization. The feasibility of the approach is demonstrated using data from 3 empirical and 2 synthetic systems.

Abstract

Multi-edge networks capture repeated interactions between individuals. In social networks, such edges often form closed triangles, or triads. Standard approaches to measure this triadic closure, however, fail for multi-edge networks, because they do not consider that triads can be formed by edges of different multiplicity. We propose a novel measure of triadic closure for multi-edge networks of social interactions based on a shared partner statistic. We demonstrate that our operalization is able to detect meaningful closure in synthetic and empirical multi-edge networks, where common approaches fail. This is a cornerstone in driving inferential network analyses from the analysis of binary networks towards the analyses of multi-edge and weighted networks, which offer a more realistic representation of social interactions and relations.

Abstract

We introduce a broad class of random graph models: the generalised hypergeometric ensemble (GHypEG). This class enables to solve some long-standing problems in random graph theory. First, GHypEG provides an elegant and compact formulation of the well-known configuration model in terms of an urn problem. Second, GHypEG allows incorporating arbitrary tendencies to connect different vertex pairs. Third, we present the closed-form expressions of the associated probability distribution ensures the analytical tractability of our formulation. This is in stark contrast with the previous state-of-the-art, which is to implement the configuration model by means of computationally expensive procedures.

Abstract

The inference of network topologies from relational data is an important problem in data analysis. Exemplary applications include the reconstruction of social ties from data on human interactions, the inference of gene co-expression networks from DNA microarray data, or the learning of semantic relationships based on co-occurrences of words in documents. Solving these problems requires techniques to infer significant links in noisy relational data. In this short paper, we propose a new statistical modeling framework to address this challenge. It builds on generalized hypergeometric ensembles, a class of generative stochastic models that give rise to analytically tractable probability spaces of directed, multi-edge graphs. We show how this framework can be used to assess the significance of links in noisy relational data. We illustrate our method in two data sets capturing spatio-temporal proximity relations between actors in a social system. The results show that our analytical framework provides a new approach to infer significant links from relational data, with interesting perspectives for the mining of data on social systems.

Abstract

We introduce a statistical method to investigate the impact of dyadic relations on complex networks generated from repeated interactions. It is based on generalised hypergeometric ensembles, a class of statistical network ensembles developed recently. We represent different types of known relations between system elements by weighted graphs, separated in the different layers of a multiplex network. With our method we can regress the influence of each relational layer, the independent variables, on the interaction counts, the dependent variables. Moreover, we can test the statistical significance of the relations as explanatory variables for the observed interactions. To demonstrate the power of our approach and its broad applicability, we will present examples based on synthetic and empirical data.

Abstract

Statistical ensembles define probability spaces of all networks consistent with given aggregate statistics and have become instrumental in the analysis of relational data on networked systems. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these important data science techniques, in this article we introduce generalized hypergeometric ensembles, a framework of analytically tractable statistical ensembles of finite, directed and weighted networks. This framework can be interpreted as a generalization of the classical configuration model, which is commonly used to randomly generate networks with a given degree sequence or distribution. Our generalization rests on the introduction of dyadic link propensities, which capture the degree-corrected tendencies of pairs of nodes to form edges between each other. Studying empirical and synthetic data, we show that our approach provides broad perspectives for community detection, model selection and statistical hypothesis testing.