Many classic networks grow by hooking small components via vertices. We introduce a class of networks that grows by fusing the edges of a small graph to an edge chosen uniformly at random from the network. For this random edge-hooking network, we study the local degree profile, that is, the evolution of the average degree of a vertex over time. For a special subclass, we further determine the exact distribution and an asymptotic gamma-type distribution. We also study the “core,” which consists of the well-anchored edges that experience fusing. A central limit theorem emerges for the size of the core.

At the end, we look at an alternative model of randomness attained by preferential hooking, favoring edges that experience more fusing. Under preferential hooking, the core still follows a Gaussian law but with different parameters. Throughout, Pólya urns are systematically used as a method of proof.

The special issue of “Networks in space and in time: methods and applications” contributes to the debate on contextual analysis in network science. It includes seven research papers that shed light on the analysis of network phenomena studied within geographic space and across temporal dimensions. In these papers, methodological issues as well as specific applications are described from different fields. We take the seven papers, study their citations and texts, and relate them to the broader literature. By exploiting the bibliographic information and the textual data of these seven documents, citation analysis and lexical correspondence analysis allow us to evaluate the connections among the papers included in this issue.

Despite the importance of diverse expertise in helping solve difficult interdisciplinary problems, measuring it is challenging and often relies on proxy measures and presumptive correlates of actual knowledge and experience. To address this challenge, we propose a text-based measure that uses researcher’s prior work to estimate their substantive expertise. These expertise estimates are then used to measure team-level expertise diversity by determining similarity or dissimilarity in members’ prior knowledge and skills. Using this measure on 2.8 million team invented patents granted by the US Patent Office, we show evidence of trends in expertise diversity over time and across team sizes, as well as its relationship with the quality and impact of a team’s innovation output.

Polarization makes it difficult to form positive relationships across existing groups. Decreasing polarization may improve political discourse around the world. Polarization can be modeled on a social network as structural balance, where the network is composed of groups with positive links between all individuals in the group and negative links with all others. Previous work shows that incorporating attributes of individuals usually makes structural balance, and hence polarization, harder to achieve. That work examines only a limited number and types of attributes. We present a generalized model and a simulation framework to analyze the effect of any type of attribute, including analytically as long as an expected value can be written for the type of attribute. As attributes, we consider people’s (approximately) immutable characteristics (e.g., race, wealth) and such opinions that change more slowly than relationships (e.g., political preferences). We detail and analyze five classes of attributes, recapitulating the results of previous work in this framework and extending it. While it is easier to prevent than to destabilize polarization, we find that usually the most effective at both are continuous attributes, followed by ordered attributes and, finally, binary attributes. The effectiveness of unordered attributes varies depending on the magnitude of negative impact of having differing attributes but is smaller than of continuous ones. Testing the framework on network structures containing communities revealed that destroying polarization may require introducing local tensions. This model could be used by policymakers, among others, to prevent and design effective interventions to counteract polarization.

Bipartite networks represent pairwise relationships between nodes belonging to two distinct classes. While established methods exist for analyzing unipartite networks, those for bipartite network analysis are somewhat obscure and relatively less developed. Community detection in such instances is frequently approached by first projecting the network onto a unipartite network, a method where edges between node classes are encoded as edges within one class. Here we test seven different projection schemes by assessing the performance of community detection on both: (i) a real-world dataset from social media and (ii) an ensemble of artificial networks with prescribed community structure. A number of performance and accuracy issues become apparent from the experimental findings, especially in the case of long-tailed degree distributions. Of the methods tested, the “hyperbolic” projection scheme alleviates most of these difficulties and is thus the most robust scheme of those tested. We conclude that any interpretation of community detection algorithm performance on projected networks must be done with care as certain network configurations require strong community preference for the bipartite structure to be reflected in the unipartite communities. Our results have implications for the analysis of detected community structure in projected unipartite networks.

The degree distribution of the neighbors of nodes in a network is a theoretically important tool that is invoked in diverse studies in network science, such as epidemics, network resilience, network search and observability, network synchronization, random walks, opinion dynamics, and other dynamical systems on networks. Many real networks grow, and their properties pertaining to the said phenomena evolve. There is a paucity of theoretical research on how the evolution of these properties depend upon time and upon the structure of the initial network. This paper addresses this problem by providing the first theoretical study of the temporal evolution of the nearest-neighbor degree distribution for arbitrary networks (with any size) in arbitrary times. The posited results enable the analysis of the structural properties of growing networks in the short-time and intermediary time regimes, which are typically ignored in favor of the steady state. We corroborate the solutions via Monte Carlo simulations on various topologies. As a byproduct of the obtained solutions, we also demonstrate that the existing result in the literature on the asymptotic behavior of the Pearson coefficient of growing networks under the preferential attachment mechanism is incorrect, and we present the correct solution.

We report on an interview method using photo-based network elicitation and a landmark anchoring event to collect data on relationship change in ego networks retrospectively. Using the wedding albums of married or formerly married respondents, we populate a network from many years ago with persons pictured in the album and then collect data about each respondent’s relationship with each person at the time of the wedding and at the time of the interview. This data collection method mitigates many of the problems associated with retrospective data collection and does not have the logistical difficulties associated with panel studies. Our findings show that this method is successful in collecting significant numbers of connections that have undergone change, and especially reductions in activity along various dimensions.

Data-driven analysis of complex networks has been in the focus of research for decades. An important area of research is to study how well real networks can be described with a small selection of metrics, furthermore how well network models can capture the relations between graph metrics observed in real networks. In this paper, we apply machine-learning techniques to investigate the aforementioned problems. We study 500 real-world networks along with 2000 synthetic networks generated by four frequently used network models with previously calibrated parameters to make the generated graphs as similar to the real networks as possible. This paper unifies several branches of data-driven complex network analysis, such as the study of graph metrics and their pair-wise relationships, network similarity estimation, model calibration, and graph classification. We find that the correlation profiles of the structural measures significantly differ across network domains and the domain can be efficiently determined using a small selection of graph metrics. The structural properties of the network models with fixed parameters are robust enough to perform parameter calibration. The goodness-of-fit of the network models highly depends on the network domain. By solving classification problems, we find that the models lack the capability of generating a graph with a high clustering coefficient and relatively large diameter simultaneously. On the other hand, models are able to capture exactly the degree-distribution-related metrics.

Previous research stresses the importance of social networks for obesity. We draw on friendship data from 18,133 adolescents in four European countries to investigate the relationship between individuals’ body mass index (BMI) and the BMI of their friends. Our study reveals strong evidence for BMI clustering in England, Germany, the Netherlands, and Sweden; adolescents tend to be friends with others who have a similar BMI. Furthermore, we extend current debate and explore friendship characteristics that moderate the relationship between social networks and BMI. We demonstrate that BMI clustering is more pronounced in (1) strong compared to weak friendships and (2) between adolescents of the same biological sex. These findings indicate thatmore research on social networks and health is needed which distinguishes between different kinds of relationships.

Nowadays, modern Earth Observation systems continuously generate huge amounts of data. A notable example is the Sentinel-2 Earth Observation mission, developed by the European Space Agency as part of the Copernicus Programme, which supplies images from the whole planet at high spatial resolution (up to 10 m) with unprecedented revisit time (every 5 days at the equator). In this data-rich scenario, the remote sensing community is showing a growing interest toward modern supervised machine learning techniques (e.g., deep learning) to perform information extraction, often underestimating the need for reference data that this framework implies. Conversely, few attention is being devoted to the use of network analysis techniques, which can provide a set of powerful tools for unsupervised information discovery, subject to the definition of a suitable strategy to build a network-like representation of image data. The aim of this work is to provide clues on how Satellite Image Time Series can be profitably represented using complex network models, by proposing a methodology to build a multilayer network from such data. This is the first work to explore the possibility to exploit this model in the remote sensing domain. An example of community detection over the provided network in a real-case scenario for the mapping of complex land use systems is also presented, to assess the potential of this approach.

The link prediction task has found numerous applications in real-world scenarios. However, in most of the cases like interactions, purchases, mobility, etc., links can re-occur again and again across time. As a result, the data being generated is excessively large to handle, associated with the complexity and sparsity of networks. Therefore, we propose a very fast, memory-less, and dynamic sampling-based method for predicting recurring links for a successive future point in time. This method works by biasing the links exponentially based on their time of occurrence, frequency, and stability. To evaluate the efficiency of our method, we carried out rigorous experiments with massive real-world graph streams. Our empirical results show that the proposed method outperforms the state-of-the-art method for recurring links prediction. Additionally, we also empirically analyzed the evolution of links with the perspective of multi-graph topology and their recurrence probability over time.

We study the persistence of network segregation in networks characterized by the co-evolution of vertex attributes and link structures, in particular where individual vertices form linkages on the basis of similarity with other network vertices (homophily), and where vertex attributes diffuse across linkages, making connected vertices more similar over time (influence). A general mathematical model of these processes is used to examine the relative influence of homophily and influence in the maintenance and decay of network segregation in self-organizing networks. While prior work has shown that homophily is capable of producing strong network segregation when attributes are fixed, we show that adding even minute levels of influence is sufficient to overcome the tendency towards segregation even in the presence of relatively strong homophily processes. This result is proven mathematically for all large networks and illustrated through a series of computational simulations that account for additional network evolution processes. This research contributes to a better theoretical understanding of the conditions under which network segregation and related phenomenon—such as community structure—may emerge, which has implications for the design of interventions that may promote more efficient network structures.

Graphlet counting is a widely explored problem in network analysis and has been successfully applied to a variety of applications in many domains, most notatbly bioinformatics, social science, and infrastructure network studies. Efficiently computing graphlet counts remains challenging due to the combinatorial explosion, where a naive enumeration algorithm needs O(Nk) time for k-node graphlets in a network of size N. Recently, many works introduced carefully designed combinatorial and sampling methods with encouraging results. However, the existing methods ignore the fact that graphlet counts and the graph structural information are correlated. They always consider a graph as a new input and repeat the tedious counting procedure on a regular basis even if it is similar or exactly isomorphic to previously studied graphs. This provides an opportunity to speed up the graphlet count estimation procedure by exploiting this correlation via learning methods. In this paper, we raise a novel graphlet count learning (GCL) problem: given a set of historical graphs with known graphlet counts, how to learn to estimate/predict graphlet count for unseen graphs coming from the same (or similar) underlying distribution. We develop a deep learning framework which contains two convolutional neural network models and a series of data preprocessing techniques to solve the GCL problem. Extensive experiments are conducted on three types of synthetic random graphs and three types of real-world graphs for all 3-, 4-, and 5-node graphlets to demonstrate the accuracy, efficiency, and generalizability of our framework. Compared with state-of-the-art exact/sampling methods, our framework shows great potential, which can offer up to two orders of magnitude speedup on synthetic graphs and achieve on par speed on real-world graphs with competitive accuracy.

The network Laplacian spectral density calculation is critical in many fields, including physics, chemistry, statistics, and mathematics. It is highly computationally intensive, limiting the analysis to small networks. Therefore, we present two efficient alternatives: one based on the network’s edges and another on the degrees. The former gives the exact spectral density of locally tree-like networks but requires iterative edge-based message-passing equations. In contrast, the latter obtains an approximation of the spectral density using only the degree distribution. The computational complexities are 𝒪(|E|log(n)) and 𝒪(n), respectively, in contrast to 𝒪(n3) of the diagonalization method, where n is the number of vertices and |E| is the number of edges.

A stream of research on co-authorship, used as a proxy of scholars’ collaborative behavior, focuses on members of a given scientific community defined at discipline and/or national basis for which co-authorship data have to be retrieved. Recent literature pointed out that international digital libraries provide partial coverage of the entire scholar scientific production as well as under-coverage of the scholars in the community. Bias in retrieving co-authorship data of the community of interest can affect network construction and network measures in several ways, providing a partial picture of the real collaboration in writing papers among scholars. In this contribution, we collected bibliographic records of Italian academic statisticians from an online platform (IRIS) available at most universities. Even if it guarantees a high coverage rate of our population and its scientific production, it is necessary to deal with some data quality issues. Thus, a web scraping procedure based on a semi-automatic tool to retrieve publication metadata, as well as data management tools to detect duplicate records and to reconcile authors, is proposed. As a result of our procedure, it emerged that collaboration is an active and increasing practice for Italian academic statisticians with some differences according to the gender, the academic ranking, and the university location of scholars. The heuristic procedure to accomplish data quality issues in the IRIS platform can represent a working case report to adapt to other bibliographic archives with similar characteristics.

This paper proposes that common measures for network transitivity, based on the enumeration of transitive triples, do not reflect the theoretical statements about transitivity they aim to describe. These statements are often formulated as comparative conditional probabilities, but these are not directly reflected by simple functions of enumerations. We think that a better approach is obtained by considering the probability of a tie between two randomly drawn nodes, conditional on selected features of the network. Two measures of transitivity based on correlation coefficients between the existence of a tie and the existence, or the number, of two-paths between the nodes are developed, and called “Transitivity Phi” and “Transitivity Correlation.” Some desirable properties for these measures are studied and compared to existing clustering coefficients, in both random (Erdös–Renyi) and in stylized networks (windmills). Furthermore, it is shown that in a directed graph, under the condition of zero Transitivity Correlation, the total number of transitive triples is determined by four underlying features: size, density, reciprocity, and the covariance between in- and outdegrees. Also, it is demonstrated that plotting conditional probability of ties, given the number of two-paths, provides valuable insights into empirical regularities and irregularities of transitivity patterns.

Personalized PageRank has found many uses in not only the ranking of webpages, but also algorithmic design, due to its ability to capture certain geometric properties of networks. In this paper, we study the diffusion of PageRank: how varying the jumping (or teleportation) constant affects PageRank values. To this end, we prove a gradient estimate for PageRank, akin to the Li–Yau inequality for positive solutions to the heat equation (for manifolds, with later versions adapted to graphs).

Critical cascades are found in many self-organizing systems. Here, we examine critical cascades as a design paradigm for logic and learning under the linear threshold model (LTM), and simple biologically inspired variants of it as sources of computational power, learning efficiency, and robustness. First, we show that the LTM can compute logic, and with a small modification, universal Boolean logic, examining its stability and cascade frequency. We then frame it formally as a binary classifier and remark on implications for accuracy. Second, we examine the LTM as a statistical learning model, studying benefits of spatial constraints and criticality to efficiency. We also discuss implications for robustness in information encoding. Our experiments show that spatial constraints can greatly increase efficiency. Theoretical investigation and initial experimental results also indicate that criticality can result in a sudden increase in accuracy.

We develop a model of strategic network formation of collaborations to analyze the consequences of an understudied but consequential form of heterogeneity: differences between actors in the form of their production functions. We also address how this interacts with resource heterogeneity, as a way to measure the impact actors have as potential partners on a collaborative project. Some actors (e.g., start-up firms) may exhibit increasing returns to their investment into collaboration projects, while others (e.g., established firms) may face decreasing returns. Our model provides insights into how actor heterogeneity can help explain well-observed collaboration patterns. We show that if there is a direct relation between increasing returns and resources, start-ups exclude mature firms and networks become segregated by types of production function, portraying dominant group architectures. On the other hand, if there is an inverse relation between increasing returns and resources, networks portray core-periphery architectures, where the mature firms form a core and start-ups with low-resources link to them.

Social influence is frequently measured through an ego's direct ties. Although influence may also stem from an ego's indirect ties, reference group, and casual contacts, it is difficult to capture their impact using existing network methods. We identify and trace the influence stemming from an ego's “familiar others,” consisting of those socially similar individuals with whom the ego comes in contact at school, but does not necessarily share a relationship. To evaluate the role of familiar others, we investigate unhealthy weight behaviors in adolescence using data from the National Longitudinal Study of Adolescent to Adult Health. Our results demonstrate that familiar others' unhealthy weight-related behaviors are strong predictors of the ego's own weight behaviors, net of immediate alters' behaviors, and individual-level characteristics. Further, we find that this relationship is stronger and more robust than that between egos and their direct ties. These results suggest that familiar others constitute a key source of social influence that is distinct from the influence of network alters.