ABSTRACT. In this paper, we study the competition between external controllers with fixed campaign budgets in which one of the controllers attempts to maximize the share of a desired opinion in a group of agents who exchange opinions on a social network subject to voting dynamics. In contrast to allocating all the budgets at the beginning of the campaign, we consider a version of a temporal influence maximization problem, where the controller has the flexibility to determine when to start control. We then explore the dependence of optimal starting times to achieve maximum vote shares at a finite time horizon on network heterogeneity. We find that, for short time horizons, maximum influence is achieved by starting relatively later on more heterogeneous networks than in less homogeneous networks, while the opposite holds for long time horizons.

ABSTRACT. Web-based interactions allow agents to coordinate and to take actions (change state) jointly, i.e., to participate in collective action such as a protest, facilitating spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the types (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally different from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Common knowledge arises in many settings in practice, yet there are few operational models that can be used to compute contagion dynamics. Moreover, these models utilize different mechanisms for driving contagion. We evaluate the three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook. We evaluate these mechanisms, on five social (media) networks with wide-ranging properties. We demonstrate that different mechanisms can produce widely varying behaviors in terms of the extent of contagion spreading and the speed of contagion transmission.

ABSTRACT. See extended abstract.

ABSTRACT. Often in the setting of human-based interactions, the existence of a temporal hierarchy of information plays an important role in diffusion and opinion dynamics within communities. For example at the individual agent level, more recently acquired information may exert greater influence during social decision-making processes. To facilitate further exploration of this effect, we introduce an efficient method for modelling temporally asynchronous opinion updates, where the timing of updates depends on when incoming opinion states are received from neighbours. The framework enables the introduction of information arrival-time lag by means of lag-vectors. These are used to weight the relevance of information received by agents, based on the delay between its receipt and the subsequent opinion update. The temporal dynamics (i.e. the times at which information is transmitted) are governed by an underlying algebraic structure called max-plus algebra. We investigate the resulting continuous opinion dynamics under the max-plus regime using a modified Hegselmann-Krause model, replacing the conventional confidence-interval based on the distance between opinions with one based instead on the recency of information received by agents.

ABSTRACT. We study the problem of a population with a certain degree of prevalence of an infection, in which several types and qualities of tests to detect it are available. We obtain analytic results in the number of testing required for different pool testing strategies. We present numerical results for the case of mixed testing strategies, which include using in the first stage a faster and more readily available test (with a higher degree of false positives and negatives) using multiple testing of pool samples to increase confidence levels, followed by a second stage of retesting the individuals in the identified infected samples with more precise tests We explored the optimization of the parameters of the number of repetition of tests, levels of confidence required, and pool sample sizes for different levels of prevalence of the infection. These mixed strategies allow to identify with greater success and more efficiency the infected cases, and could be of help in mid-size populations and are relevant for massive tests in schools and university campuses.

ABSTRACT. This article proposes an approach to compare semantic networks using concept-centered sub-networks. We illustrate the approach on written and interview texts from an ethnographic study of flood management practice in England.

ABSTRACT. Important scientific findings are sometimes resisted at first by the scientific community: This is so-called delayed recognition. A sleeping beauty, a representative phenomenon of delayed recognition, is a paper reported by a prince paper. The sleeping beauty includes many key concepts of breakthroughs for scientific problems. Many patterns illustrate how princes discover sleeping beauties, but no systematic approach has been used to identify sleeping beauties because so many patterns show how a prince paper awakens a sleeping beauty. This study explores classification of sleeping beauties and their prince pairs using citation rarity among clusters. Results show that citation rarity corresponds to the types of contributions to prince papers. Rare citations explore methodological insights into prince fields, although common citations can lead to rediscovery of the core concepts of a sleeping beauty. Furthermore, Informatics and Materials Sciences include major explorations that include citations to sleeping beauties. Biological subjects find key papers through rediscovery. Findings suggest that different categories of citation yield sleeping beauties of different types.

ABSTRACT. With the advent of social media for cooking recipes, considerable attention has recently been devoted to food science and computing. From the perspective of complex network science, ingredient pairings in recipes were analyzed. Recently, Benson et al provided a framework for analyzing a dataset recording time-stamped interactions among a set of elements as a temporal higher-order network in terms of simplicial closure, which is a distinctive phenomenon of higher-order structure and cannot be captured by traditional network analysis like triadic closure. Using real data, they demonstrated that higher-order network evolution is fundamentally different from dyadic network evolution. According to their definition, only one interaction among a set of n-nodes causes a (higher-order) n-link. However, it should be unsuitable for a trend analysis of ingredient combinations in recipes on social media since their observation can often contain anomalous noise events. In this paper, aiming to reveal statistically significant properties of their temporal changes, we introduce a novel concept of significant (higher-order) n-link. Using recipe datasets from social media, we analyze the characteristics of significant higher-order ingredient networks as compared with conventional ones from the viewpoints of temporal stability and simplicial closure.

ABSTRACT. We have studied turbulent plasma as a complex system applying the method known as Horizontal Visibility Graph (HVG) to obtain the Kullback-Leibler Divergence (KLD) as a first approach to characterize the irreversibility of the time series of the magnetic fluctuations. For this, we have developed the method on Particle In Cell (PIC) simulations for a magnetized plasma. Our numerical results show that low irreversibility values are verified for magnetic field time series associated with Maxwellian distributions and in the case of kappa distributions the KLD value increases for decreasing kappa value.

ABSTRACT. We find that the visibility algorithm is a useful way to study the light curves of variable stars, showing interesting features, some of them universal, for all the stars studied, whereas others seem to discriminate between such types. It is also interesting that this method exhibits similar results for the three different ways to deal with the gaps, meaning that the —always difficult problem to resolve— gap existence is not too important for this construction, and that we can obtain valuable information from these light curves regardless of observational gaps.

ABSTRACT. The Global Trade Network (WTN) is a network of exchange flows among countries whose topological and statistical properties are a valuable source of information. Degree and strength are key magnitudes to understand its structure. We have built a stochastic generative model that yields synthetic networks that closely mimic the properties of annual empirical data. Agreement between empirical and synthetic networks is checked using the available series from 1962 to 2017. One of the properties of the WTN is inequality. This model can explain how it is a self-sustained property of the newtork and suggests possible strategies to tackle it. We apply a mild mitigation method and assess the quantitative impact on the Gini index. The results of the numerical experiments show that trade agreements between un- derrepresented countries with no regional limitations may have a sensible larger impact on reducing inequality of the international trade network. Improvement ratio, without regional restrictions, follows a quadratic pattern an so, small actions may be quite ef- fective if they are focused on the group of extremely poor nodes. Results also confirm one of the network’s most relevant properties: self-fulfilling structural inequality.

ABSTRACT. While real life market interactions tend to be selective in the sense that not all suppliers get in touch with all customers and vica versa, standard economic analysis frequently assume away this incompleteness and use models where consumers have access to all product varieties and producers supply the entire market. An interesting aspect of this incomplete connectedness is price heterogeneity: if supplier-buyer interactions are not complete in the above sense, consumers make decisions on different information bases with respect to prices and if rational suppliers take these differences into consideration then heterogeneous prices may arise from the specific network structure on which market interactions are based.

In this study we build a simple model of monopolistic competition where the network structure of supplier-buyer interactions is explicitly taken into account. In this model framework we then analyze the existence and properties of equilibrium prices. In particular, we are interested in the distribution of prices and the extent to which the selective nature of market interactions can give rise to price dispersion. This attempt fits well into the literature on price heterogeneity and incomplete information concerning competitive market structures.

The results of this study are two-fold: (i) We analytically prove that the equilibrium price vector exists under non-restrictive conditions of the market structure and (ii) we show with simulations that incomplete market structure gives rise to price heterogeneity and this price heterogeneity hinges on the density of the interaction network while the asymmetry of the network plays a minor role.

ABSTRACT. As the corporate ownership network has rapidly expanded at the global scale in the recent, the international society has just begun to notice its impact on our society. Impacts of globalized ownership network, however, are hard to measure because the structure of ownership networks has become increasingly complex with the rise of a passive investment strategy and because diversified portfolio investing strategies call for complex financial instruments such as a fund of funds and exchange-traded funds (ETF). Yet, the awareness of Environment, Social, and Governance (ESG) investing makes it increasingly important than ever before to understand the structure of the global ownership network and how capital flows therein to shape the distribution of corporate control and the associated risks and responsibilities. We use three kinds of databases. (1) We obtain global corporate network data, including 66 million shareholders, from the Bureau van Dijk's Orbis database. (2) We use the data on ETFs and mutual funds that are traded in the US and Japan. These are about 800 thousand financial instruments in our database that supply money into the corporate ownership network through the asset management nodes (companies). A classic example that goes against the spirit of ESG is investment in military companies. (3) We have collected 3793 companies globally whose military terms are included in their company profiles in the Orbis database. These contain companies that are designated by the US Department of Commerce as the companies that contribute to the Chinese government’s procurement of commodities and technologies for military end-use. As an example, we investigate the structure of the corporate ownership network in which investment money flows from U.S. and Japanese investors to Chinese munition companies through financial instruments such as ETFs. The analysis of the shortest (not fastest) path from asset management companies to a Chinese munition company reveals that no asset manager either in the US or Japan directly invests in any Chinese munition companies with one link of ownership. That is, no Chinese munitions company's stock was included in the ETFs or mutual funds listed in the US and Japanese markets. However, all the asset managers have at least the first path through which their equity stakes eventually reach a Chinese munitions company with the second or further apart links in the global ownership network. This result points to an important social consequence, namely causing the gap between the power of corporate control and the stewardship responsibility. In the ideal world where the investors who strive for socially responsible investing should be empowered by their own equity stakes to make positive impacts on corporate activities in the ESG issues. However, two obstacles encourage decoupling of equity stakes and social responsibilities and socially responsible investors become incapable of making positive impacts with their investing strategy. The first obstacle is the fact that ETFs and other similar financial instruments separate capital and corporate control. The second is the complexity of ownership network itself. The complexity of the ownership network is likely to prevent the ultimate owners from knowing its own potential.

ABSTRACT. Social distancing measures adopted to combat the COVID-19 pandemic have created severe disruptions to economic output. These economic shocks are highly industry-specific and apply to both supply and demand. Since firms are embedded in production networks, these direct shocks will propagate upstream and downstream. We show that standard IO models which allow for binding demand and supply constraints yield infeasible solutions when applied to empirical data from the United Kingdom. We then introduce a mathematical optimization procedure which is able to determine optimal and feasible market allocations, giving a lower bound on total shock propagation. We find that even in this best-case scenario network effects substantially amplify the initial shocks. To obtain more realistic model predictions, we study the propagation of shocks out of equilibrium by imposing different rationing rules on firms if they are not able to satisfy incoming demand. Our results show that overall economic impacts depend strongly on the emergence of input bottlenecks, making the rationing assumption a key variable in economic predictions.

ABSTRACT. Due to the COVID-19 pandemic, economists are increasingly focusing on the structure of global supply chains and the economic effects of the virus. A series of recent studies have indicated that economic lockdown in a country can significantly influence the performance of other countries indirectly, through the production networks. With this perspective in mind, this research presented a method to measure the level of a country’s independence of global supply chains which can be used to decompose this independence into two factors: the share of domestic inputs and the dominance of domestic sales. The results reveal that countries are very heterogeneous in terms of the two factors and the extent of independence. The most independent country is China because the Chinese sectors are closely connected as suppliers in their production network. The US economy is on a similar level with respect to the ratio of domestic inputs, however, due to the structure of the production networks, especially in the case of manufacturing industries, the Chinese economy is less dependent on the global supply chains.

ABSTRACT. Complex networks have been successfully used to describe the spread of diseases in populations of interacting individuals. Conversely, pairwise interactions are often not enough to characterize social contagion processes such as opinion formation or the adoption of novelties, where complex mechanisms of influence and reinforcement are at work. I will first discuss a higher-order model of social contagion in which a social system is represented by a simplicial complex and contagion can occur through interactions in groups of different sizes. Numerical simulations of the model on both empirical and synthetic simplicial complexes highlight the emergence of novel phenomena such as a discontinuous transition induced by higher-order interactions. I will show analytically that the transition is discontinuous and that a bistable region appears where healthy and endemic states co-exist. This result can help explaining why critical masses are required to initiate social changes. I will then show how the presence of higher-order interaction can affect the stability of a synchronised state in a simplicial complex of coupled dynamical systems.

ABSTRACT. Changes in the structure of observed social and complex networks' structure can indicate a significant underlying change in an organization, or reflect the response of the network to an external event. Automatic detection of change points in evolving networks is rudimentary to the research and the understanding of the effect of such events on networks. Here we present an easy-to-implement and fast framework for change point detection in evolving temporal networks. Unlike previous approaches, our method is size agnostic, and does not require either prior knowledge about the network's size and structure, nor does it require obtaining historical information or nodal identities over time. We tested it over both synthetic data derived from dynamic models and two real datasets: Enron email exchange and AskUbuntu forum. Our framework succeeds with both precision and recall and outperforms previous solutions.

ABSTRACT. In the study of complex networks, simple local heterogeneous interactions favor highly complicated and non-linear dynamics. In this paper, we take advantage of recent advances presented by Rosas et al [Physical Review E, 100, 032305] to capture the fundamentals of dynamics: high-order interdependencies. In particular, the phase diagram of Random Boolean Networks is described in terms of the information shared between multiple nodes. We found that the critical point between ordered and chaotic regimes is well defined by a balance between redundancy and synergy, for both normal and scale-free topologies. In addition, particular network structures are identified that characterize the behavior of high-order interdependencies in each dynamic regime.

ABSTRACT. The massive spread of online social media platforms has favored the emergence of social media giants, like Facebook, Twitter, Instagram. These companies have been the center of many scandals related to privacy issues, data ownership and censorship. The issues that stem from their centralized architecture, brought the spotlight on alternative solutions based on decentralized or distributed architectures. In these alternative social media platforms, the data is not owned by a single company, the open nature makes censorship harder and users can profit from their contents. Here we focus on a specific solution - Steemit - built on top of a public blockchain, linked to the Steem cryptocurrency. In fact, in Steemit, the participation and the content quality are rewarded with a cryptocurrency through a network- and user-based voting system. This way, the network structure, the dynamics on top of it and the cryptocurrency market are strongly coupled. Such an interplay is the focus of the paper; specifically, we study the impact of the cryptocurrency Steem on the social network growth, using more than 4 years of data extracted directly from the Steem Blockchain. We find that the growth of the network is strongly tied to the fluctuations in Steem cryptocurrency price: it can be observed that rising Steem prices trigger the network growth, and similarly, when Steem value drops, so does the network's growth. We also find evidence of a lead-follow relationship between Steem price and users' behavior: our study suggests that the full impact of the Steem cryptocurrency price can be observed within 3-4 weeks. So essentially, the blockchain-based social network Steemit represents a valuable case study among the emerging online social media, where network dynamics and economic/financial aspects are strongly intertwined; and where the underlying blockchain is an unprecedented source of data for measuring such interplay.

ABSTRACT. Stream graphs model highly dynamic networks in which nodes and/or links arrive and/or leave over time. Connected components in stream graphs were defined recently, but no algorithm was provided to compute them. We present here several solutions with polynomial time and space complexities, each with its own strengths and weaknesses. We provide an implementation and experimentally compare the algorithms in a wide variety of practical cases. In addition, we propose an approximation scheme that significantly reduces computation costs, and gives even more insight on the dataset.

ABSTRACT. In this paper we derive an analytical expression for the mean load at each node of an arbitrary undirected graph for the uniform multicommodity flow problem under random walk routing. We show the mean load is linearly dependent on the nodal degree with a common multiplier equal to the sum of the inverses of the non-zero eigenvalues of the graph Laplacian. Even though some aspects of the mean load value, such as linear dependence on the nodal degree, are intuitive and may be derived from the equilibrium distribution of the random walk on the undirected graph, the exact expression for the mean load in terms of the full spectrum of the graph has not been known before. Using the explicit expression for the mean load, we give asymptotic estimates for the load on a variety of graphs whose spectral density are well known. We conclude with numerical computation of the mean load for other well-known graphs without known spectral densities.

ABSTRACT. Network science provides effective tools to model and analyze complex systems. However, the increasing size of real-world networks becomes a major obstacle in order to understand their structure and topological features. Therefore, reducing the original network into a smaller one while preserving its information is an important issue. Extracting the so-called backbone of a network is a very challenging problem that is generally solved either by coarse-graining or filter-based methods. Coarse-graining methods reduce the network size by grouping similar nodes, while filter-based methods map the network by discarding nodes or edges based on a statistical property. In this work, we propose and investigate one filter-based method exploiting the overlapping community structure in order to extract the backbone in weighted networks. In the proposed method, called "overlapping nodes ego backbone", the backbone is formed simply from the set of overlapping nodes and their neighbors. It is based on the results of a previous study showing that the overlapping nodes are neighbors of the highly connected nodes (hubs) of the network. Indeed, hubs and overlapping nodes are located at the heart of the network. In this method, the links with low weights are removed from the network as long as a backbone with a single connected components are preserved. The purpose of this approach is to extract the overlapping nodes given their role connecting various modules of nodes, the highly connected nodes in the network as well as the most relevant connections. Experiments have been performed on real-world weighted networks originating from various domains (social, co-appearance, collaboration, biological, and technological) and different sizes. Results of the comparison with the disparity filter method, which is considered as one of the most influential alternative filtering methods demonstrate the greater ability of the proposed backbone extraction method to uncover the most relevant parts of the network.

ABSTRACT. Identifying influential nodes in networks is of great significance. Such nodes play an enormous role in epidemic spreading, information diffusion, disease formation, and robustness assessment of networks. Hierarchy and centrality measures are the wo main research approaches to quantify node influence. Plenty of work has been devoted on the relationship between centrality measures, however no investigation has been conducted yet to uncover how hierarchy and centrality relate. In this work, an extensive analysis on hierarchy and centrality measures is performed to assess their interactions using real-world networks from diverse domains. Results show that centrality and hierarchy measures can exhibit complementary views of the network shaped by the macroscopic topological properties. Density and transitivity give a clear guide about which centrality measures and which hierarchy measures should be used in practical applications

ABSTRACT. The 3-clique formation, a natural phenomenon in real-world networks, is typically measured by the local clustering coefficient, where the focal node serves as the centre-node in an open triad. The local closure coefficient provides a novel perspective, with the focal node serving as the end-node. It has shown some interesting properties in network analysis, yet it cannot be applied to complex directed networks. Here, we propose the directed closure coefficient as an extension of the closure coefficient in directed networks, and we extend it into weighted and signed networks. In order to better use it in network analysis, we introduce further the source closure coefficient and the target closure coefficient. Our experiments show that the proposed directed closure coefficient provides complementary information to the classic directed clustering coefficient. We also demonstrate that adding closure coefficients leads to better performance in link prediction task in most directed networks.

ABSTRACT. The coefficients that characterize the small-world phenomenon synthesizes the network giving a unique associated value but do not provide an idea of the dispersion of the nodes of the network regarding each of these measures, and therefore about the heterogeneity of the network. In this paper, some equality measures are introduced in order to provide a more profound insight into the structure of complex networks.

ABSTRACT. The shortest-path, commute time, and diffusion distances on undirected graphs have been widely employed in applications such as dimensionality reduction, link prediction, and trip planning. Increasingly, there is interest in using asymmetric structure of data derived from Markov chains and directed graphs, but few metrics are specifically adapted to this task. We introduce a metric on the state space of any ergodic, finite-state, time-homogeneous Markov chain and, in particular, on any Markov chain derived from a directed graph. Our construction is based on hitting probabilities, with nearness in the metric space related to the transfer of random walkers from one node to another at stationarity. Notably, our metric is insensitive to shortest and average path distances, thus giving new information compared to existing metrics. We use possible degeneracies in the metric to develop an interesting structural theory of directed graphs and explore a related quotienting procedure. Our metric can be computed in O(n^3) time, where n is the number of states, and in examples we scale up to n=10,000 nodes and 38M edges on a desktop computer. In several examples, we explore the nature of the metric, compare it to alternative methods, and demonstrate its utility for weak recovery of community structure in dense graphs, visualization, structure recovering, dynamics exploration, and multiscale cluster detection.

ABSTRACT. The medical referrals between primary care doctor and specialist affect many aspects of patient care, such as quality of care, patient satisfaction and health care costs, etc. In this work, we hypothesize that the social network of medical doctors can influence the referral process. We analyse primary-specialty referrals through transaction data over medical appointments gathered between 2012 and 2017 in all hospital centers of a European private health provider. The main objective of the study is to discover patterns and hidden mechanisms in the primary-specialist referrals to improve efficiency of health care services. First, we carry out exploratory data analysis and search for patterns or interesting features of the data and afterwords we create and analyse the doctor's social network and the referrals network. We learn the representation of the referral network using a Graph Neural Network (GNN). This work addresses the discovery of important patterns in medical referrals to, in a future work, improve the efficiency of collaboration within organizations.

ABSTRACT. In this work we address algorithmic fairness concerns that arise when graph nodes are ranked based on their structural relatedness to a personalized set of query ones. In particular, we aim to mitigate disparate impact, i.e. the difference in average rank between nodes of a sensitive attribute compared to the rest, while also preserving node rank quality. To do this, we introduce a personalization editing mechanism whose parameters can be adjusted to help the ranking algorithm achieve a variety of trade-offs between fairness constraints and rank changes. In experiments across three real-world social graphs and two base ranking algorithms, our approach outperforms baseline and existing methods in uniformly mitigating disparate impact, even when personalization suffers from extreme bias. In particular, it achieves higher trade-offs between fairness and rank quality and manages to preserve most of node rank quality when a constrained amount of disparate impact is allowed.

ABSTRACT. Influence maximization is the task of finding the smallest set of nodes to be activated in a social network such that their aggregated influence can trigger an activation cascade that reaches the targeted network coverage, where threshold rules determine the outcome of influence. This problem is NP-hard and it has generated a significant amount of recent research on finding efficient heuristics. We use a Balance Index algorithm that relies on three parameters to tune its performance to the given network structure. We propose using a supervised Machine-Learning approach for such tuning. We propose a random-walk-based graph sampling that quickly creates snapshots of large scale real-world networks to be used as training data. We found the most influential graph features for the parameter tuning. We also validated the applicability of the synthetic network trained machine-learning model to various real-world networks.

ABSTRACT. Image classification is an important, real-world problem that arises in many contexts. To date, convolutional neural networks (CNNs) are the state-of-the-art deep learning method for image classification since these models are naturally suited to problems where the coordinates of the underlying data representation have a grid structure. On the other hand, in recent years, there is a growing interest in mapping data from different domains to graph structures. Such approaches proved to be quite successful in different domains including physics, chemoinformatics and natural language processing. In this paper, we propose to represent images as graphs and capitalize on well-established neural network architectures developed for graph-structured data to deal with image-related tasks. The proposed models are evaluated experimentally in image classification tasks, and are compared with standard CNN architectures. Results show that the proposed models are very competitive, and yield in most cases accuracies better or comparable to those of the CNNs.

ABSTRACT. In contrast to other domains, recommender systems in health sector may benefit particularly from the incorporation of health domain knowledge, as it helps to provide meaningful and personalised recommendations. With re-cent advances in representation learning enabling the hierarchical embed-ding of health knowledge into the hyperbolic Poincaré space, this work proposes a recommender system for patient-doctor matchmaking based on patients’ individual health profiles and consultation history, together with the enriched Poincaré embeddings of the ICD-9 codes through the represen-tation learning. The proposed model outperforms its conventional counter-part in terms of recommendation accuracy and has several important busi-ness implications for improving patient-doctor relationship.

ABSTRACT. Human social networks frequently give rise to long-tailed and non-stationary information spreading, but most methods of analysis and decision making typically assume stationary, concentrated distributions. Similarly, wisdom of the crowd phenomena are usually analyzed as a single trial with a fixed information sharing network whereas dynamic networks and importance of long-term repeated-trial performance are major feature of human societies. I will discuss new theoretical results on optimal tuning of information sharing networks while accounting for long-tailed distributions. Finally, I will show that these new theoretical results provide a good model for how humans tune their social networks for better performance in non-stationary and long-tailed environments.

ABSTRACT. Organizational networks are often hierarchical by nature as individuals take on roles or functions at various job levels. Prior stud- ies have used either text-level (e.g., sentiment, affect) or structural-level features (e.g., PageRank, various centrality metrics) to identify influen- tial nodes in a social network. In this study, we use a combination of these two levels of information to develop a novel ranking method that combines sentiment analysis and PageRank to infer node-level influence in a real-world organizational network. We detect sentiment scores for all actor pairs based on the content of their communication exchanges, and calculate their influence index using an enhanced PageRank method. Finally, we group individuals into distinct clusters according to their in- fluence index. Compared to established network metrics designed or used to infer formal and informal influence, our metric achieves the highest accuracy for inferring formal influence (60.7%) and second highest for inferring informal influence (69.0%). Our approach shows that a combi- nation of text-level and structural-level information is effective for finding individuals’ job levels in an organizational network.

ABSTRACT. Military confrontation is one of the key factors that has shaped human history. While warfare in the post-Cold War era have decreased, internal wars and low-intensity conflicts carried out by nonstate armed groups (NAGs) against nation states have become increasingly common. NAGs can include rebel, insurgent, guerrilla, or terrorist groups that engage in violent activity targeting the government, citizens, or institutions of nation-states. Unlike the warfare that has received extensive analyses, the hidden relations of NAGs and their supporting host states (HSs) are yet to be revealed. We study the bipartite network of NAGs and the HSs and its evolution over a large timespan by employing the latest pattern detection algorithm. We discover that the network has experienced a dynamical process that involves both highly biased attachment and detachment. Analogous to what is typically observed in ecological mutualistic and parasitic relations, a peculiar architecture showing both nested and modular patterns is persistently shown in a large portion of the timespan. Quantifying the supporting network provides an important perspective towards the comprehension of the origin, evolution and termination of this global hidden power.

ABSTRACT. Social networks amplify inequalities by fundamental mechanisms of social tie formation such as homophily and triadic closure. Together these forces sharpen social segregation reflected in network fragmentation. Geographical impediments such as distance and physical or administrative boundaries are also known sharpen social segregation. Yet, little is known about the joint relation between physical geography, social network structure, and inequalities. In this paper we analyze an online social network and find that the fragmentation of social networks is significantly higher in towns in which residential neighborhoods are divided by physical barriers such as rivers and railroads and are relatively distant from the center of town. Towns in which amenities are spatially concentrated are also more socially segregated. Using a two-stage model, we demonstrate that urban topology has a significant relationship with income inequality via social network fragmentation. In sum, social network structure functions as a link between physical urban geography and inequalities.

ABSTRACT. Behavioral gender differences are known to exist for a wide range of human activities, including the way people communicate, move, provision themselves, or organize their leisure activities. Using mobile phone data from $1.2$ million devices in Austria (15\% of the population) across the COVID-19 crisis, we derive a number of measures that allow us to quantify and approximate gender-specific patterns of communication intensity (frequency and length), mobility, and proxies for online activity, and sleeping behavior. At the beginning of the crisis, Austria experienced a severe nation-wide lock-down with severe implications on public and private life. We can not only show the resilience of the behavior with respect to shock imposed by the lock-down, we see drastic effects in the gender-differences during the different phases of the pandemic. We find that after the lock-down gender differences in mobility and communication patterns increased massively while sleeping patterns and circadian rhythms tend to synchronize. In particular, mobility declined massively for both genders, however, females tend to move much less than males. After the lock-down, males returned back to normal up to XXX days quicker than females. These differences were driven by the young and adolescent population. During the lock-down, females had fewer but longer phone calls than males, and showed a stronger tendency to avoid recreational areas. We discuss the findings in the light of gender-specific coping strategies in response to stress and crisis.

ABSTRACT. Societies are complex and their properties emerge from the interplay and weavingof individual actions. Rewards are key to understand people’s choices and decisions.For instance, individual preferences of where to live may lead to the emergence of so-cial segregation. In this paper, we combine Reinforcement Learning (RL) with AgentBased Modeling (ABM) in order to address the self-organizing dynamics of social seg-regation and explore the space of possibilities that emerge from considering differenttypes of incentives. Our model promotes the creation of interdependencies and inter-actions among multiple agents of two different kinds that segregate from each other.For this purpose, agents use Deep Q-Networks (DNN) to make decisions inspired onthe rules of the Schelling Segregation model and rewards for interactions. Despite thesegregation reward, our experiments show that spatial integration can be achieved byestablishing interdependencies among agents of different kinds. They also reveal thatsegregated areas are more probable to host older people than diverse areas, which at-tract younger ones. Through this work, we show that the combination of RL and ABMcan create an artificial environment for policy makers to observe potential and existingbehaviors associated to rules of interactions and reward.

ABSTRACT. Different types of people learn how to make decisions differently, especially when making complex choices informed by social network interactions. The details about these differences are still largely unknown. In this paper, we investigate how differences in cooperativeness are linked with our deliberation process in different social contexts. We study how long it takes for subjects to learn to play the game and how this depends on the network structure. The Drift Diffusion Model (DDM) (Ratcliff, 2016) gives us a unique perspective and ability to quantify the subject's cautiousness by observing response times. We found that subjects playing Prisoner’s Dilemma in a network act more cautious with respect to a pairwise setting. Moreover, subjects start to learn the game within 10-30 rounds, and from this moment on, they do not change much how they play the game. We then categorise subjects in those who cooperate/defect most of the time regardless of what others do and those who adapt their actions to what the other players do in the previous round. Our DDM analysis predicatively shows that those who react to others’ actions perceive a difference in their cautiousness between playing in a fixed-neighbors setting versus a shuffled-neighbors network setting. We thus hypothesize that these settings enable building a trust relationship which plays a role in this case.

ABSTRACT. Suicide notes represent the last remaining trace of mental states of people who committed suicide. Investigating these notes is key to understanding how these individualsperceived their own choice, its context and its framing. To this aim, we build on the framework of cognitive network science for quantitatively extracting key ideas and emotions present in 139 genuine suicide notes. This work relies on cognitive network science, a field merging data science, psychology and complex networks in order to understand cognition through large-scale knowledge graphs and language processing. Unraveling these cognitive networks of concepts becomes key for opening a window onto people’s minds and understanding them through data-driven analyses. This is also the main motivation of our approach, which overlaps with previous studies in psychology relying on human coding for understanding the language of suicide notes. In comparison to these approaches, our key innovation lies in using automatic tools for quantitative reconstructing the se-mantic frames and emotional perceptions attributed by authors to key aspects of their suicidal ideation.

ABSTRACT. What traits make users appealing as potential teammates? How do the traits that users seek out in teammates stay constant and differ as the task changes? Our study explores the social networks and skills involved in teammate selection. We performed a quasi-experimental study to analyze teammate choices for three tasks: launching a start-up, surviving in a jungle, and running an election campaign. We conducted our study in one graduate and two undergraduate classes, where students self-assembled into teams using a team recommender software. We analyzed our results using Exponential Random Graph Models (ERGMs). Our results indicate that (a) among all three tasks, prior relationships were important, while (b) the importance of certain project skills varied across the three task types when choosing potential teammates.

ABSTRACT. Introduction

The advent of social media and microblogging platforms over the last decade has brought fundamental changes to the way people access and share information, com- municate, etc. According to Eurobarometer, the percentage of Europeans making daily use of social networks to access news has increased from 18% in 2010 to 42% in 2017 [1]. So far, however, researchers have mainly focused on the behaviour of social me- dia users, individuating several stylized facts. For example, it has been observed that online users are more likely to select information adhering to their system of beliefs and joining groups (the so-called “echo chambers”) supporting it; these groups, in turn, are often found to be polarized, hence promoting an approach to discussions which is strongly negatively biased[2]. Relatively less attention has, instead, been paid to the semantic aspect of online conversations and its nexus with the relationships amongst users participating to them.

Our contribution aims at filling this gap by exploring the structural properties of both the networks of actors and the networks of topics induced by the Italian debate about migration, across the period May-November 2019. For the present analysis, we have focused on Twitter, a choice driven by the evidence that it is massively used during political debates[3], by the vast majority of public figures (e.g. political leaders, journalists, official media accounts), to provide visibility to their statements. Amongst all types of interaction modes characterizing the Twitter platform, the current study grounds on retweets, i.e. a relational mechanism which is particularly insightful when studying collective political identities[4].

Results

Following the approach of [5, 6], we have considered the bipartite networks of veri- fied users retweeted by non-verified users at a monthly time scale and proceeded in a two-step fashion. First, we have obtained the corresponding set of (monopartite) projections on the layer of verified accounts, by comparing the empirical number of times any couple of verified users have been retweeted by the same non-verified users with the outcome of a properly-defined benchmark model (in our case, the so-called Bipartite Configuration Model [7]); then, we have run the Louvain community detection algorithm on the obtained projections.

Remarkably, the detected groups - named discursive communities and interpreted as clusters of users sharing similar contents, in turn able to trigger a discussion - can be identified with (members and supporters of) the main Italian political parties. As reported in Figure 1, the projection “summing up” the entire observation period (and obtained by properly combining the monthly projections) is characterized by the presence of five largest communities, i.e. the supporters of “Movimento 5 Stelle” (Five Star Movement) (yellow), the supporters of far-right parties (green), the supporters of center-left parties (red), a community of media and NGO accounts (purple) and a community of politicians and supporters of the center-right party “Forza Italia” (Go Italy). Moreover, at a finer grained level (i.e., the monthly time scale), our analysis clearly spots out the effects of the 2019 Italian government crisis, leading the center-left leaning community to split into two sub-communities. In order to provide a deeper insight into the online discussions characterizing each discursive community, we have also analyzed the structure of the corresponding monthly semantic networks which are obtained by projecting each bipartite user-hashtag network on the hashtags layer (as hashtags play a central role in the Twitter environment, we have defined the nodes of our semantic networks to be precisely the hashtags extracted from the text of the collected tweets).

Out of the four different recipes employed in our work to obtain the semantic net- works, here we consider the application of the Naive projection, obtained by linking any two hashtags sharing a non-negative number of users, and the one obtained by em- ploying the Bipartite Configuration Model [7] as a benchmark. The latter projection lets the most persistent (groups of) hashtags emerge: as shown in Figure 2, the bulk of the discussion characterizing the far-right leaning community, in June 2019, is represented by keywords such as #primagliitaliani, #iostoconsalvini, #oggivotolega. Interestingly, the k-shell decomposition of the semantic networks obtained by link- ing any two hashtag sharing a non-negative number of users has revealed the presence of a core-periphery structure (i.e. a bunch of very well-connected vertices, linked to a group of low-degree, loosely inter-linked nodes) characterizing the monthly activity of each discursive community.

ABSTRACT. We analyze the evolution of Twitter activities in Slovenia in recent years. We construct networks, with Twitter users as nodes, and retweet relations as edges. We detect communities and influential users in them, and track how they evolve during times of political changes and start of the Covid-19 pandemic. We observe that most of the influential users are related to politics around which communities emerge, that the political polarization is increasing, and that the right leaning Twitter users are more active.

ABSTRACT. Gentrification is a contentious issue which local governments struggle to deal with because warning signs are not always visible. Unlike current literature that utilises solely socio-economic data, we introduce the use of large-scale spatiotemporal mobility data to predict which neighbourhoods of a city will gentrify. More specifically, from mobility data, which is associated with the exchange of ideas and capital between neighbourhoods, we construct mobility networks. Features are extracted from these mobility networks and used in gentrification prediction, which is framed as a binary classification. As a case study, we use the Taxi & Limousine Commission Trip Record Data to predict which census tracts would gentrify in New York City from 2010 to 2018, and show that considering network features alongside socio-economic features leads to a significant improvement in prediction performance.

ABSTRACT. All interesting and fascinating collective properties of a complex system arise from the intricate way in which its components interact. Various systems in physics, biology, social sciences and engineering have been successfully modelled as networks of coupled dynamical systems, where the graph links stand for pairwise interactions. This is, however, too strong a limitation, as recent studies have revealed that higher-order many-body interactions are present in social groups, ecosystems and in the human brain, and they actually affect the emergent dynamics of all these systems. I will discuss a general framework that allows to study coupled dynamical systems accounting for the precise microscopic structure of their interactions at any possible order. Namely, I will conider an ensemble of identical dynamical systems, organized on the nodes of a simplicial complex, and interacting through synchronization-non-invasive coupling function. The simplicial complex can be of any dimension, meaning that it can account, at the same time, for pairwise interactions (networks), three-body interactions and so on. In such a broad context, a recent collaboration of mine has shown that complete synchronization, a circumstance where all the dynamical units arrange their evolution in unison, exists as an invariant solution, and has given the necessary condition for it to be observed as a stable state in terms of a Master Stability Function. This generalizes the existing results valid for pairwise interactions (i.e. graphs) to the case of complex systems with the most general possible architecture. Moreover, we show how the approach can be simplified for specific, yet frequently occurring, instances, and we verify all our theoretical predictions in synthetic and real-world systems. Given the completely general character of the method proposed, our results contribute to the theory of dynamical systems with many-body interactions and can find applications in an extremely wide range of practical cases.

ABSTRACT. In this article, our ultimate goal is to transform a graph's adjacency matrix into a distance matrix. Because cluster density is not observable prior to the actual clustering, our goal is to find a distance whose pairwise minimization will lead to densely connected clusters. Our thesis is centered on the widely accepted notion that strong clusters are subgraphs with high induced subgraph density. We posit that vertices sharing more connections are closer to each other than vertices sharing fewer connections. This definition of distance differs from the usual shortest-path distance. At the cluster level, our thesis translates into low mean intra-cluster distances, which reflect high densities. We compare three distance measures from the literature. Our benchmark is the accuracy of each measure's reflection of intra-cluster density, when aggregated (averaged) at the cluster level. We conduct our tests on synthetic graphs, where clusters and intra-cluster density are known in advance. In this article, we restrict our attention to unweighted graphs with no self-loops or multiple edges. We examine the relationship between mean intra-cluster distances and intra-cluster densities. Our numerical experiments show that Jaccard and Otsuka-Ochiai offer very accurate measures of density, when averaged over vertex pairs within clusters.

ABSTRACT. Autocratic cooperation is difficult to study. Democratic states usually disfavor autocratic cooperation partners because they are perceived as less reliable and do not sign agreements with them. While it is challenging to capture autocratic cooperation with traditional approaches such as signed alliance treaties, co-sponsorship at the United Nations General Assembly (UNGA) offers a valuable alternative. UNGA co-sponsorship is less binding than alliances, allowing states to cooperate more freely with one another. What is more, states are required to choose cooperation partners actively. This allows us to study the extent that autocracies cooperate more with each other at a venue that overcomes common restrictions to autocratic cooperation. We construct co-sponsorship networks at the UNGA and use the Leiden algorithm to identify community clusters. Our multiclass random forest classification model supports our assumption and shows that regime type is an important factor in explaining cooperation at the UNGA.

ABSTRACT. Community detection is a significant research problem in Network Science since it identifies groups of nodes that may have certain functional importance - termed communities. Our goal is to further study this problem from a different perspective related to the questions of the cause of participation within a community. To this end, we apply the framework of causality and responsibility developed by Halpern and Pearl~\cite{10.1093/bjps/axi147}. We provide an algorithm-semi-agnostic framework for computing causes and responsibility of participation within a community. To the best of the authors' knowledge, this is the first work that examines causality in community detection. Furthermore, the proposed framework is easily adaptable to be also used in other network processing operations apart from community detection.

ABSTRACT. We propose a community detection algorithm for hypergraphs. The main feature of this algorithm is that it can be adjusted to various scenarios depending on how often vertices in one community share hyperedges with vertices from other community.

ABSTRACT. In a real-world network, overlapping structures are important for understanding the community. In many different situations,a node may join or leave and this defines sub-communities of different sizes.In this paper, we propose a preference implication based-method for generating overlapping structures based on a local function optimization approach. We introduce some parameters in our novel method to design the communities according to a threshold. This method allows us to control the size and number of these overlapping regions. Theνallowsus to design the sub-communities. This framework is ease for detecting communities in a scale-free network case. We set our experiments using artificial and real network data with a size between ≈15 to ≈10000. In our findings, we found a good relationship ofνand overlapping nodes in communities. We govern our procedure using α parameter as well. We can say that the preference is stronger when ν is greater than 0.5 and the value of α between 0.20 and 0.80. The third parameter δ which controls the intensity of community membership defines the degree of relationship of a node to a community. The communities detected by the preference implication method obey a power law in the community size distribution.

ABSTRACT. Security and privacy have been major concerns of Online Social Networks (OSN). Individual users as well as organizations utilize OSNs, such as Facebook, Twitter, and LinkedIn, to share information with other users within their networks. While sharing information, users are not always aware of the fact that an innocent action on their post by a direct friend such as a comment or a share may turn the post transparent to someone outside their network. In previous work we have devised a comprehensive Trust-based model that combines Role based Access Control for the direct circle of friends and Flow Control for the friends' networks. In this paper we reinforce this model by analyzing its strength in terms of OSN features. We simulate attack scenarios carried out by a community of malicious users that attempt to fake the OSN features of the model. We analyze the attack of an alleged trustworthy clique of adversaries and show the futility of such an attack, due to the strength of the model's parameters and combination of Trust, Access Control and Flow Control. We also demonstrate the robustness of the model when facing an optimized attack, which carefully selects the best network nodes to compromise, as determined by the minimal vertex cover algorithm.

ABSTRACT. To analyze the dynamics of network formation and evolution, we propose a novel way to analyze edges by depreciating their value over time. Using this approach which, we suggest, is particularly relevant in the context of social media-based networks, network measures such as authority can be calculated on a continuous basis and show developments over time without relying on snapshots for temporal analysis of networks.

ABSTRACT. The tail shape of size distributions is a matter of ongoing discussion. Here we propose to tackle this problem by dissecting the most important mechanisms behind the observed patterns. We show that the size of twitter cascades is well approximated by a model of exponential growth with a decaying rate. It is not necessary to include any information about the underlying node distribution of the social network. We define a new measure of tweet popularity which, unlike cascade size, is not power law distributed and hence may be used to infer features that determine tweet success.

ABSTRACT. Review platforms employ a voting mechanism, in which the crowd is invited to upvote reviews that they find useful. In this research, we investigate the attributes of over 1.2M reviews written by more than 327K users over three different review platforms. We find that useful reviews, on average, are authored by a small group of authors and that the best predictor for the success of a review is the author's history. The emotional effect of a review, measured by the amount of expressed emotions according to Plutchik wheel of discrete emotions, is of a lesser explaining value, but still performs better than textual features, and more so for services (as opposed to products). Regression analysis for the exact score reveals that apart from the cross-platform predictive power of the author's impact and review length, search goods and experience goods differ in what makes them useful. Structural review features are significant for experience goods but insignificant for search products. Discrete negative emotions correlate positively with the usefulness of reviews, more so for experience goods.

ABSTRACT. Analysis of media partisanship during election requires an objective measurement of political bias that frames the content of information conveyed to the audience. In this study, we propose a method for political stance detection of online news outlets based on the behavior of their audience in social media. The method consists of 3 processing stages, namely hashtag-based user label-ing, network-based user labeling, and media classification. Evaluation results show that the proposed method is very effective in detecting the political affilia-tion of Twitter users as well as predicting the political stance of news media. Overall, the stance of media in the spectrum of political valence confirms the general allegations of media partisanship during the 2019 Indonesian election. Further elaboration regarding news consumption behavior shows that low-credibility news outlets tend to have extreme political positions, while partisan readers tend not to question the credibility of the news sources they share.

ABSTRACT. The standard and extensively used method for generating artificial networks is the LFR graph generator. Unfortunately, this model has some scalability limitations and it is challenging to analyze it theoretically. Finally, the mixing parameter, has a non-obvious interpretation and so can lead to unnaturally-defined networks.

In this extended abstract, we provide an alternative random graph model with community structure and power-law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD) graph. The model generates graphs with similar properties as the LFR. We test the speed of our algorithm and do a number of experiments comparing basic properties of both ABCD and LFR. The conclusion is that these models produce graphs with comparable properties but ABCD is fast, easy to generate using parallel algorithms, and has desirable theoretical properties.

ABSTRACT. A remarkable approach for modelling the statistical properties of real networks is provided by hyperbolic network models, centred around the idea of placing nodes in a low dimensional hyperbolic space and introducing random connections according to probabilities that depend on the hyperbolic distance between the nodes. The random graphs generated by e.g. the popularity-similarity optimisation (PSO) model and the S1/H2 model are known to be small-world, highly clustered and scale-free at the same time, reproducing the most important universal features often seen in real systems. In the present work, we find that the hyperbolic networks obtained from the above models also contain communities for a rather wide range of the model parameters, which comes as a surprise as the appearance of communities was certainly not an intention at the construction of these models. Nevertheless, since communities usually provide very important units at an intermediate level of the structural organisation of real systems as well, these results make the hyperbolic approach even more suitable for modelling real networks than thought before.

ABSTRACT. Mutualism is a vital element that comprises natural and social systems. As evidenced in plant-pollinator relations and designer-contractor partnerships, the actors typically exhibit an ordered pattern of collective interactions. The interspecific relation can be represented by a bipartite network of multiple species (plant and animal guilds for example). Such networks consistently express highly modular and nested structures, compared with their randomized counterparts. Whether and how the two structural properties of mutualistic networks can emerge out of a unified mechanism however remains unclear. Here, we elucidate a unified principle that explains how high-level mutualistic network patterns can emerge from interactions that adapt based on the niches of individual actors. Key dynamical properties are revealed at different time scales, ranging from network stability to environmental impacts. We further demonstrate that such adaptiveness is crucial for preserving the network structure under invasions.

ABSTRACT. %% This is LLNCS.DEM the demonstration file of %% the LaTeX macro package from Springer-Verlag %% for Lecture Notes in Computer Science, %% version 2.4 for LaTeX2e as of 16. April 2010 %% \documentclass{llncs} % \usepackage{mathptmx} % selects Times Roman as basic font \usepackage{helvet} % selects Helvetica as sans-serif font \usepackage{courier} % selects Courier as typewriter font \usepackage{type1cm} % activate if the above 3 fonts are not available on your system \usepackage{makeidx} % allows index generation \usepackage{graphicx} % standard LaTeX graphics tool when including figure files \usepackage{multicol} % used for the two-column index \usepackage[bottom]{footmisc}% places footnotes at page bottom \usepackage{subfigure} \usepackage{amsfonts} \usepackage[cmex10]{amsmath}

\begin{document} \title{Statistical properties of edges and bredges in configuration model networks} % \titlerunning{Articulation points and bredges} % abbreviated title (for running head) % also used for the TOC unless % \toctitle is used % \author{Ofer Biham\inst{1} \and Haggai Bonneau\inst{1} Eytan Katzav\inst{1} \and Reimer K\"uhn \inst{2} } % \authorrunning{Ofer Biham et al.} % abbreviated author list (for running head) % %%%% list of authors for the TOC (use if author list has to be modified) \tocauthor{Ofer Biham, Haggai Bonneau, Eytan Katzav and Reimer K\"uhn} % \institute{Racah Institute of Physics, The Hebrew University, Jerusalem 9190401, Israel\\ \email{biham@phys.huji.ac.il},\\ %WWW home page: \texttt{http://cond-mat.phys.huji.ac.il/ofer/} \and Mathematics Department, King’s College London, Strand, London WC2R 2LS, UK} \maketitle

% %\section{Introduction} %

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Since the integrity of most networks (particularly transportation and communication networks) is essential for their functionality, bredges are vulnerable links that play an important role in network collapse processes. Therefore, the abundance and properties of bredges affect the resilience of the network to both inadvertent failures and deliberate attacks. We present analytical results for the statistical properties of bredges in configuration model networks \cite{Bonneau2020}. Using a generating function approach based on the cavity method, we calculate the probability $\widehat P(e \in {\rm B})$ that a random edge $e$ in a configuration model network with degree distribution $P(k)$ is a bredge (B). We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. %We calculate the probability %$\widehat P(e \in {\rm B},{\rm GC})$ %that a random edge is a bredge that resides on the giant component %and the probability %$\widehat P(e \in {\rm B},{\rm FC})$ %that a random edge is a bredge that resides on %one of the finite components.

In Fig. \ref{fig:1} we present an Erd{\H o}s-R\'enyi (ER) network of $N=100$ nodes with mean degree $c=1.7$. The giant component of this network coexists with many finite tree components. The non-bredge edges (solid lines) connect pairs of nodes that reside on the 2-core of the giant component \cite{Newman2008}. The giant component is decorated by tree branches, on which all the edges are bredges. The bredge that connects each tree branch to the 2-core of the giant component is called root bredge (dashed line). The end-node of the root bredge that resides on the 2-core is called root end-node. All the other bredges (dotted lines) connect pairs of nodes that reside on the tree branches, which are not on the 2-core. The distinction between root bredges and all the other bredges on the giant component may be useful for optimized dismantling algorithms \cite{Braunstein2016} and targeted attacks \cite{Cohen2001,Yuan2016}. This is due to the fact that the deletion of a root bredge disconnects the whole tree branch that is held by this bredge. In contrast, random deletion of bredges may require a large number of deletion steps in order to chop each tree branch from the 2-core of the giant component.

\begin{figure} \centerline{ \includegraphics[width=7.0cm]{fig1.eps} } \caption{ The structure of an instance of an ER network of $N=100$ nodes with mean degree $c=1.7$, which exhibits a coexistence between a giant component and finite tree components. The non-bredge edges (solid lines) connect pairs of nodes that reside on the 2-core of the giant component. The 2-core exhibits a complex web of cycles. The root bredges (dashed lines) connect the tree branches on the giant component to the 2-core. All the other bredges (dotted lines) connect pairs of nodes on that reside on the tree branches of the giant component and pairs of nodes on the finite tree components. } \label{fig:1} \end{figure}

In Fig. \ref{fig:2} we present analytical reults for the probability $\widehat P(e \in {\rm B})$ (solid line) that a randomly sampled edge in an ER network is a bredge as a function of the mean degree $c$. The probability $\widehat P(e \in {\rm B})$ can be expressed as a sum of two components: the probability $\widehat P(e \in {\rm B} , {\rm GC})$ (dashed line) that a randomly sampled edge is a bredge that resides on the giant component, and the probability $\widehat P(e \in {\rm B} , {\rm FC})$ (dotted line) that a randomly sampled edge is a bredge that resides on one of the finite components. The analytical results (solid, dashed and dotted lines) are in excellent agreement with the results of computer simulations (circles), performed for an ensemble of ER networks of $N=10^4$ nodes.

\begin{figure} \centerline{ \includegraphics[width=8cm]{fig2.eps} } \caption{ The probability $\widehat P(e \in {\rm B})$ (solid line) that a randomly sampled edge in an ER network is a bredge, as a function of the mean degree $c$; The probability $\widehat P(e \in {\rm B})$ is equal to the sum of two components: the probability $\widehat P(e \in {\rm B} , {\rm GC})$ (dashed line) that a randomly sampled edge is a bredge that resides on the giant component, and the probability $\widehat P(e \in {\rm B} , {\rm FC})$ (dotted line) that a randomly sampled edge is a bredge that resides on one of the finite components. The analytical results (solid, dashed and dotted lines) are in excellent agreement with the results of computer simulations (circles), performed for an ensemble of ER networks of $N=10^4$ nodes. } \label{fig:2} \end{figure}

In order to analyze degree-degree correlations between the end-nodes of bredges, we calculate the joint degree distribution $\widehat P(k,k' | {\rm B})$ of the end-nodes $i$ and $i'$ of a random bredge. We also calculate the joint degree distribution $\widehat P(k,k'|{\rm B},{\rm GC})$ of the end-nodes of bredges and the joint degree distribution $\widehat P(k,k'|{\rm NB},{\rm GC})$ of the end-nodes of non-bredge (NB) edges on the giant component. Surprisingly, it is found that the degrees $k$ and $k'$ of the end-nodes of bredges are correlated, while the degrees of the end-nodes of non-bredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the degree-degree correlation function $\Gamma({\rm B},{\rm GC})$ between the end-nodes of bredges, also called the assortativity coefficient \cite{Newman2002}, and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (ER networks), an exponential distribution and a power-law distribution (scale-free networks). %The implications of these results are discussed in the context of common %attack scenarios and network dismantling processes.

The properties of bredges in a wide range of real-world empirical networks were recently studied \cite{Wu2018}. The fraction of bredges in each empirical network was calculated using an algorithm based on depth-first search. An ensemble of configuration model networks, whose degree distribution coincides with the degree sequence of the empirical network, was generated using degree-preserving randomization. The fraction of bredges in each ensemble was calculated both numerically and using a generating function formalism. It was found that the fraction of bredges in the randomized ensembles is very similar to their fraction in the corresponding empirical networks. This indicates that the information about the number of bredges is captured in the degree distribution. Thus, configuration model networks are likely to provide useful predictions for the statistical properties of bredges in empirical networks and their effect on the resilience or vulnerability of these networks to failures and attacks.

%Therefore, correlations and other structural %properties that distinguish an empirical network %from the corresponding configuration model network were %found to have little effect on the number of bredges.

% %\section{Results} %

%\begin{figure} %\centering %\includegraphics[]{} %\caption{} %\label{ } % Give a unique label %\vspace{-0.4cm} %\end{figure}

%\begin{equation} %\label{eq:} %\end{equation}

%\paragraph{Summary}

\begin{thebibliography}{10} \providecommand{\url}[1]{\texttt{#1}} \providecommand{\urlprefix}{URL }

\bibitem{Bonneau2020} H. Bonneau, O. Biham, R. K\"uhn and E. Katzav, Statistical analysis of edges and bredges in configuration model networks, {\it Phys. Rev. E} {\bf 102}, 012314 (2020).

\bibitem{Newman2008} M.E.J. Newman and G. Ghoshal, Bicomponents and the robustness of networks to failure, {\it Phys. Rev. Lett.} {\bf 100}, 138701 (2008)

\bibitem{Braunstein2016} A. Braunstein, L. Dall'Asta, G. Semerjian and L. Zdeborov\'a, Network dismantling. {\it Proc. Natl. Acad. Sci. USA} {\bf 113}, 12368 (2016).

\bibitem{Cohen2001} R. Cohen, K. Erez, D. ben-Avraham and S. Havlin, Breakdown of the Internet under intentional attack, {\it Phys. Rev. Lett.} {\bf 86}, 3682 (2001).

\bibitem{Yuan2016} X. Yuan, Y. Dai, H.E. Stanley and S. Havlin, $k$-core percolation on complex networks: Comparing random, localized, and targeted attacks, {\it Phys. Rev. E} {\bf 93}, 062302 (2016).

\bibitem{Newman2002} M.E. J.Newman, Assortative mixing in networks, {\it Phys. Rev. Lett.} {\bf 89}, 208701 (2002)

\bibitem{Wu2018} A.-K. Wu, L. Tian and Y.-Y. Liu, Bridges in complex networks, {\it Phys. Rev. E} {\bf 97}, 012307 (2018).

\end{thebibliography}

\end{document}

ABSTRACT. Understanding of the development of the urban fabric originally belongs to the human and social sciences (architecture, geography, history, town planning). Our aim is to study the shape of this planar network with complex system science and graph theory. The first step is to reduce the road network to a geometrical graph (intersections as nodes and street segments as edges connecting them). We seek to find the existing, intuitive, roads through a geometric approach by creating the "way", a continuous set of arcs and nodes producing a multi-scale object going from the dead end to the main avenues crossing the city. By applying classical graph theory indicators (closeness, betweeness...) and others (orthogonality, accessibility...) on this object, we obtain information on the structure and organization of this network, without being constrained by the limits of the analyzed graph as opposed to a calculation performed only on arcs. The meaningfulness of the results supports this approach and hints at the fact that this the turns, defining a topological distance, and not the metric distance along the network, which is meaningful. The distributions of indicators such as length, closeness or degree of ways each reveal patterns similar across the studied cities studied (log-normal distribution for length, normal distribution for closeness, power distribution for degree...). The question is to understand the appearance of such particular shapes of distribution for one of these indicators in order to better understand the dynamics of construction of such networks. We have chosen to look at the length of the ways. Indeed, contrary to closeness, it is a more accessible data, its calculation does not need to be integrated into the whole graph, it is also an indicator less studied in graph theory compared to the degree, which power laws can already be reproduced by several type of models (small world or quotations). It also present a more original distribution. We seek to build a model that runs through all the processes of creating ways and that can generate length distributions close to what is observed.Our models are based on the hypothesis that creating a ways by perpendicular cutting of parcels could explain this type of distribution. Each new way cuts a parcel into two smaller areas. This process is justified by the observations made in cities (the grid in the oldest urban areas in particular,like Saint-michel or Chatelet district in Paris), and physical network like clay cracks - we measured for the cracks also a length distribution close to a log-normal. We rely on models with similar dynamics in order to find this statistic, just varying the criteria for the selection of next parcel to cut. Several processes have been carried out, dividing the plots according to different characteristics: the longest side, the density of intersections in the vicinity of each plot or the number of turns to be made to access them (the integrated topological distance over the entire network). The results showed that our first hypothesis, a cut process to depend of the longest side is not enough to explain the log-normal distribution. With the density of crossroads in the proximity of each parcel, we obtain forms of networks similar to the cities (polar form) but the length distribution is still different. By substituting this density by the topological distance, we find a distribution closer to what is observed, validating the importance of this parameter in the development of roads networks.