Search

Recent advances in archaeogenomics have granted access to previously unavailable biological information with the potential to further our understanding of past social dynamics at a range of scales. However, to properly integrate these data within archaeological narratives, new methodological and theoretical tools are required. Effort must be put into finding new methods for weaving together different datasets where material culture and archaeogenomic data are both constitutive elements. This is true on a small scale, when we study relationships at the individual level, and at a larger scale when we deal with social and population dynamics. Specifically, in the study of kinship systems it is essential to contextualize and make sense of biological relatedness through social relations, which, in archaeology, is achieved by using material culture as a proxy. In this paper we propose a Network Science framework to integrate archaeogenomic data and material culture at an intrasite scale to study biological relatedness and social organization at the Neolithic site of \c{C}atalh\"oy\"uk. Methodologically, we propose the use of network variance to investigate the concentration of biological relatedness and material culture within networks of houses. This approach allowed us to observe how material culture similarity between buildings gives valuable information on potential biological relationships between individuals and how biogenetic ties concentrate at specific localities on site.

Recently, the first author proposed a measure to calculate Pearson correlations for node values expressed in a network, by taking into account distances or metrics defined on the network. In this technical note, we show that using an arbitrary choice of distances might result in imaginary or unbounded correlation values, which is undesired. We prove that this problem is solved by restricting to a special class of distances: negative type metrics. We also discuss two natural classes of negative type metrics on graphs, for which the network correlations are properly defined.

Complex networks are a useful tool to investigate various phenomena in social science, economics, and logistics. Node Vector Distance (NVD) is an emerging set of techniques allowing us to estimate the distance and correlation between variables defined on the nodes of a network. One drawback of NVD is its high computational complexity. Here we show that a subset of NVD techniques, the ones calculating the Generalized Euclidean measure on networks, can be efficiently tackled with Laplacian solvers. In experiments, we show that this provides a significant runtime speedup with negligible approximation errors, which opens the possibility to scale the techniques to large networks.

Data clustering, the task of grouping observations according to their similarity, is a key component of unsupervised learning -- with real world applications in diverse fields such as biology, medicine, and social science. Often in these fields the data comes with complex interdependencies between the dimensions of analysis, for instance the various characteristics and opinions people can have live on a complex social network. Current clustering methods are ill-suited to tackle this complexity: deep learning can approximate these dependencies, but not take their explicit map as the input of the analysis. In this paper, we aim at fixing this blind spot in the unsupervised learning literature. We can create network-aware embeddings by estimating the network distance between numeric node attributes via the generalized Euclidean distance. Differently from all methods in the literature that we know of, we do not cluster the nodes of the network, but rather its node attributes. In our experiments we show that having these network embeddings is always beneficial for the learning task; that our method scales to large networks; and that we can actually provide actionable insights in applications in a variety of fields such as marketing, economics, and political science. Our method is fully open source and data and code are available to reproduce all results in the paper.

This paper estimates the impact of violence on domestic and international migration in Mexico during 2005-2020. Unlike earlier studies, we use network analysis to quantify changes in the degree of interconnectedness among all municipalities in Mexico and with the US, breaking it down by origin-destination pairs. To identify the impact of violence on the changes of the migration network, we use instrumental variables. We exploit the exogenous variation in heroin street prices in the US, local prices of corn in Mexico, and differences in which regions received more Chinese immigrant communities during the 1930s, members of which introduced opium cultivation and drug smuggling networks in Mexico. These instruments help us identify the areas with a current presence of drug trafficking organizations and facing increases in violence. We show that municipalities that experience rises in homicide rates continue to attract immigrants within the country, but they face a larger rise in domestic emigration. The violence also discourages the return migration of Mexicans from the US and non-transit international emigration. Consistent with our findings, areas affected by violence also experience a long-term reduction in vehicle trips made in the highway network connecting them with the rest of the country.

Multiplex networks allow us to study a variety of complex systems where nodes connect to each other in multiple ways, for example friend, family, and co-worker relations in social networks. Link prediction is the branch of network analysis allowing us to forecast the future status of a network: which new connections are the most likely to appear in the future? In multiplex link prediction we also ask: of which type? Because this last question is unanswerable with classical link prediction, here we investigate the use of graph association rules to inform multiplex link prediction. We derive such rules by identifying all frequent patterns in a network via multiplex graph mining, and then score each unobserved link's likelihood by finding the occurrences of each rule in the original network. Association rules add new abilities to multiplex link prediction: to predict new node arrivals, to consider higher order structures with four or more nodes, and to be memory efficient. We improve over previous work by creating a framework that is also efficient in terms of runtime, which enables an increase in prediction performance. This increase in efficiency allows us to improve a case study on a signed multiplex network, showing how graph association rules can provide valuable insights to extend social balance theory., Comment: arXiv admin note: substantial text overlap with arXiv:2008.08351

Network science is the field dedicated to the investigation and analysis of complex systems via their representations as networks. We normally model such networks as graphs: sets of nodes connected by sets of edges and a number of node and edge attributes. This deceptively simple object is the starting point of never-ending complexity, due to its ability to represent almost every facet of reality: chemical interactions, protein pathways inside cells, neural connections inside the brain, scientific collaborations, financial relations, citations in art history, just to name a few examples. If we hope to make sense of complex networks, we need to master a large analytic toolbox: graph and probability theory, linear algebra, statistical physics, machine learning, combinatorics, and more. This book aims at providing the first access to all these tools. It is intended as an "Atlas", because its interest is not in making you a specialist in using any of these techniques. Rather, after reading this book, you will have a general understanding about the existence and the mechanics of all these approaches. You can use such an understanding as the starting point of your own career in the field of network science. This has been, so far, an interdisciplinary endeavor. The founding fathers of this field come from many different backgrounds: mathematics, sociology, computer science, physics, history, digital humanities, and more. This Atlas is charting your path to be something different from all of that: a pure network scientist.

Multiplex networks allow us to study a variety of complex systems where nodes connect to each other in multiple ways, for example friend, family, and co-worker relations in social networks. Link prediction is the branch of network analysis allowing us to forecast the future status of a network: which new connections are the most likely to appear in the future? In multiplex link prediction we also ask: of which type? Because this last question is unanswerable with classical link prediction, here we investigate the use of graph association rules to inform multiplex link prediction. We derive such rules by identifying all frequent patterns in a network via multiplex graph mining, and then score each unobserved link's likelihood by finding the occurrences of each rule in the original network. Association rules add new abilities to multiplex link prediction: to predict new node arrivals, to consider higher order structures with four or more nodes, and to be memory efficient. In our experiments, we show that, exploiting graph association rules, we are able to achieve a prediction performance close to an ideal ensemble classifier. Further, we perform a case study on a signed multiplex network, showing how graph association rules can provide valuable insights to extend social balance theory., Comment: Accepted for publication in 15th International Conference on Web and Social Media (ICWSM) 2021

Discovering communities in complex networks means grouping nodes similar to each other, to uncover latent information about them. There are hundreds of different algorithms to solve the community detection task, each with its own understanding and definition of what a "community" is. Dozens of review works attempt to order such a diverse landscape -- classifying community discovery algorithms by the process they employ to detect communities, by their explicitly stated definition of community, or by their performance on a standardized task. In this paper, we classify community discovery algorithms according to a fourth criterion: the similarity of their results. We create an Algorithm Similarity Network (ASN), whose nodes are the community detection approaches, connected if they return similar groupings. We then perform community detection on this network, grouping algorithms that consistently return the same partitions or overlapping coverage over a span of more than one thousand synthetic and real world networks. This paper is an attempt to create a similarity-based classification of community detection algorithms based on empirical data. It improves over the state of the art by comparing more than seventy approaches, discovering that the ASN contains well-separated groups, making it a sensible tool for practitioners, aiding their choice of algorithms fitting their analytic needs.

Bipartite networks are a well known strategy to study a variety of phenomena. The commonly used method to deal with this type of network is to project the bipartite data into a unipartite weighted graph and then using a backboning technique to extract only the meaningful edges. Despite the wide availability of different methods both for projection and backboning, we believe that there has been little attention to the effect that the combination of these two processes has on the data and on the resulting network topology. In this paper we study the effect that the possible combinations of projection and backboning techniques have on a bipartite network. We show that the 12 methods group into two clusters producing unipartite networks with very different topologies. We also show that the resulting level of network centralization is highly affected by the combination of projection and backboning applied.

Networks are powerful instruments to study complex phenomena, but they become hard to analyze in data that contain noise. Network backbones provide a tool to extract the latent structure from noisy networks by pruning non-salient edges. We describe a new approach to extract such backbones. We assume that edge weights are drawn from a binomial distribution, and estimate the error-variance in edge weights using a Bayesian framework. Our approach uses a more realistic null model for the edge weight creation process than prior work. In particular, it simultaneously considers the propensity of nodes to send and receive connections, whereas previous approaches only considered nodes as emitters of edges. We test our model with real world networks of different types (flows, stocks, co-occurrences, directed, undirected) and show that our Noise-Corrected approach returns backbones that outperform other approaches on a number of criteria. Our approach is scalable, able to deal with networks with millions of edges.

Tourism is one of the most important economic activities in the world: for many countries it represents the single largest product in their export basket. However, it is a product difficult to chart: "exporters" of tourism do not ship it abroad, but they welcome importers inside the country. Current research uses social accounting matrices and general equilibrium models, but the standard industry classifications they use make it hard to identify which domestic industries cater to foreign visitors. In this paper, we make use of open source data and of anonymized and aggregated transaction data giving us insights about the spend behavior of foreigners inside two countries, Colombia and the Netherlands, to inform our research. With this data, we are able to describe what constitutes the tourism sector, and to map the most attractive destinations for visitors. In particular, we find that countries might observe different geographical tourists' patterns -- concentration versus decentralization --; we show the importance of distance, a country's reported wealth and cultural affinity in informing tourism; and we show the potential of combining open source data and anonymized and aggregated transaction data on foreign spend patterns in gaining insight as to the evolution of tourism from one year to another.

In this document we describe the size of the Poblacion Flotante of Bogota (D.C.). The Poblacion Flotante is composed by people who live outside Bogota (D.C.), but who rely on the city for performing their job. We estimate the Poblacion Flotante impact relying on a new data source provided by telecommunications operators in Colombia, which enables us to estimate how many people commute daily from every municipality of Colombia to a specific area of Bogota (D.C.). We estimate that the size of the Poblacion Flotante could represent a 5.4% increase of Bogota (D.C.)'s population. During weekdays, the commuters tend to visit the city center more.

Finding talents, often among the people already hired, is an endemic challenge for organizations. The social networking revolution, with online tools like Linkedin, made possible to make explicit and accessible what we perceived, but not used, for thousands of years: the exact position and ranking of a person in a network of professional and personal connections. To search and mine where and how an employee is positioned on a global skill network will enable organizations to find unpredictable sources of knowledge, innovation and know-how. This data richness and hidden knowledge demands for a multidimensional and multiskill approach to the network ranking problem. Multidimensional networks are networks with multiple kinds of relations. To the best of our knowledge, no network-based ranking algorithm is able to handle multidimensional networks and multiple rankings over multiple attributes at the same time. In this paper we propose such an algorithm, whose aim is to address the node multi-ranking problem in multidimensional networks. We test our algorithm over several real world networks, extracted from DBLP and the Enron email corpus, and we show its usefulness in providing less trivial and more flexible rankings than the current state of the art algorithms.

The advent of social media has provided data and insights about how people relate to information and culture. While information is composed by bits and its fundamental building bricks are relatively well understood, the same cannot be said for culture. The fundamental cultural unit has been defined as a "meme". Memes are defined in literature as specific fundamental cultural traits, that are floating in their environment together. Just like genes carried by bodies, memes are carried by cultural manifestations like songs, buildings or pictures. Memes are studied in their competition for being successfully passed from one generation of minds to another, in different ways. In this paper we choose an empirical approach to the study of memes. We downloaded data about memes from a well-known website hosting hundreds of different memes and thousands of their implementations. From this data, we empirically describe the behavior of these memes. We statistically describe meme occurrences in our dataset and we delineate their fundamental traits, along with those traits that make them more or less apt to be successful.

In the last few years many real-world networks have been found to show a so-called community structure organization. Much effort has been devoted in the literature to develop methods and algorithms that can efficiently highlight this hidden structure of the network, traditionally by partitioning the graph. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition it then extracts the communities that are able to reflect only some of the features of real communities. The aim of this survey is to provide a manual for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery based on their own definition of community. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on., Comment: Published in the Statistical Analysis and Data Mining journal, Special Issue: Networks. Volume 4, Issue 5, pages 512-546, October 2011

Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighborhood, using a label propagation algorithm; finally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a limited time complexity, so that it can be used on web-scale real networks., Comment: 9 pages; Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, August 12-16, 2012