COMPLEX NETWORKS 2021: TENTH INTERNATIONAL CONFERENCE ON COMPLEX NETWORKS & THEIR APPLICATIONS
PROGRAMAUTHORSKEYWORDSSLIDES
PROGRAM FOR THURSDAY, DECEMBER 2ND
View: session overviewtalk overview
08:30-09:00 Registration
09:00-09:40 Session Speaker S5: Ginestra Bianconi - Higher-Order Networks and their Dynamics
Regino Criado
Ginestra Bianconi
Higher-order networks and their dynamics
ABSTRACT. Higher-order networks [1] describe the many-body interactions of a large variety of complex systems, ranging from the brain to collaboration networks and social contact networks. Simplicial complexes are generalized network structures which allow us to capture the combinatorial properties, the topology and the geometry of higher-order networks. In this talk we will show that simplicial complexes provide a very general mathematical framework to reveal how higher-order dynamics including synchronization and epidemic spreading depends on simplicial network topology. We will show that higher-order synchronization describing the dynamics of topological signals defined on link, triangles and higher-dimensional simplices is explosive [2-4] and we will show that this rich dynamics can have an important role for understanding brain rhythms. We will also show how epidemic spreading on higher-order networks [5] can take into account for time-dependent contacts due to co-location in space and how this modelling can help us understand the spreading dynamics of airborne diseases.
[1] G. Bianconi, Higher-order networks: An introduction to simplicial complexes (Cambridge University Press, 2021)
[2] Millán, A.P., Torres, J.J. and Bianconi, G., 2020. Explosive higher-order Kuramoto dynamics on simplicial complexes. Physical Review Letters, 124(21), p.218301.
[3] Ghorbanchian, R., Restrepo, J.G., Torres, J.J. and Bianconi, G., 2021. Higher-order simplicial synchronization of coupled topological signals. Communications Physics, 4(1), pp.1-13.
[4] Calmon, L., Restrepo, J.G., Torres, J.J. and Bianconi, G., 2021. Topological synchronization: explosive transition and rhythmic phase. arXiv preprint arXiv:2107.05107.
[5] St-Onge, G., Sun, H., Allard, A., Hébert-Dufresne, L. and Bianconi, G., 2021. Universal nonlinear infection kernel from heterogeneous exposure on higher-order networks. arXiv preprint arXiv:2101.07229.
09:40-10:40 Session Lightning L3: Networks Analysis & Measures - Diffusion & Epidemics
Huijuan Wang
María Óskarsdóttir, Kristín Eva Gísladóttir, Ragnar Stefánsson, Damian Aleman and Carlos Sarraute
Churn prediction with complex networks in mobile gaming
PRESENTER: María Óskarsdóttir
ABSTRACT. Social networks in online games are of great importance for the players and their experience. We aim to predict churn in a mobile one-versus-one game where players are matched either randomly or to a friend of choice. This results in a two layer complex network, a combination of an implicit and an explicit network. We study the importance of information from each of the two networks for churn prediction and compare influence and other social factors in the two layers on the players' behaviour.
Ollin Langle-Chimal and Nick Cheney
The effects of personal beliefs in a disease spreadingprocess
PRESENTER: Ollin Langle-Chimal
ABSTRACT. We've created a package for Network Agent-based Modeling and used it to build a model of the importance of adaptive biosecurity measures in an outbreak event that takes into account the initial personality of each agent by allowing them to follow or reject the mean behavior of their neighbors with a decaying radius of influence. We found that this personality metric has great influence on the final outcome of a spreading disease. We also studied this adaptive behavior using a serious game where the players could spend money by investing in prophylactic measures against a disease and used the results as initial conditions in our simulations.
Long Ma, Maksim Kitsak and Piet Van Mieghem
Two-population SIR model and strategies to reduce mortality in pandemics
PRESENTER: Long Ma
ABSTRACT. Despite many studies on the transmission mechanism of the Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), it remains still challenging to efficiently reduce mortality. In this work, we apply a two-population Susceptible-Infected-Removed (SIR) model to investigate the COVID-19 spreading when contacts between elderly and non-elderly individuals are reduced due to the high mortality risk of elderly people. We discover that the reduction of connections between two populations can delay the death curve but cannot well reduce the final mortality. We propose a merged SIR model, which advises elderly individuals to interact less with their non-elderly connections at the initial stage but interact more with their non-elderly relationships later, to reduce mortality. Finally, immunizing elderly hub individuals can also significantly decrease mortality.
Tatjana Petrov and Stefano Tognazzi
Lumping Reductions for Multispread in Multi-Layer Networks
PRESENTER: Stefano Tognazzi
ABSTRACT. Spreading phenomena arise from simple local interaction among a large number of actors through different networks of interactions. Computational modelling and analysis of such phenomena is challenging due to the combinatorial explosion of possible network configurations. Traditional (single layer) networks are commonly used to encode the heterogeneous relationships among agents but are limited to a single type of interaction. Multiplex Multi-Layer networks (MLNs) have been introduced to allow the modeler to compactly and naturally describe multiple types of interactions and multiple simultaneous spreading phenomena. The downside is an increase in the complexity of the already challenging task of the analysis and simulation of such spreading processes. In this paper we explore the use of lumping techniques that preserve dynamics, previously applied to Continuous Time Markov Chains (CTMC) and single layer networks to multiple spreading processes on MLNs.
Liliana Martirano and Andrea Tagarelli
Graph Node Embedding with Co-contrastive Learning for Heterogeneous Attributed Multilayer Networks
PRESENTER: Liliana Martirano
ABSTRACT. (Extended Abstract)
Keigo Kusumegi and Yukie Sano
Empirical Analysis of Acknowledgment Network and Citations
PRESENTER: Keigo Kusumegi
ABSTRACT. Acknowledgments, as well as a collaboration, are one indication of contribution to the research papers. The concept of acknowledgment can be treated as 'super-citation' [1]which shows the constitution of research formally but in the different meaning of citation or collaboration. The acknowledgments in research documents are well studied focusing on contexts, funding information [2, 3], and peer interaction communication(PIC) [4]. For contexts of acknowledgments, the pattern of acknowledgment is analyzed linguistically. Giannoni studied the words described in the acknowledgments section and found that the context of acknowledgments differs across fields [5]. For funding information, the relationships between the citation impact of the research paper and the number of funding are discussed using acknowledgments [2]. For the study of acknowledgment from the perspective of PIC, the acknowledgments are considered as the social interaction that is related to academic citation and collaboration as human interaction. However, there is little known about acknowledgments at the level of networks, especially for PIC. PIC is taken as the interaction among researchers and it is easily considered as a network of scientists, which represents the connection of scientists through the engagement of acknowledgments. The reason why acknowledgment networks have not been studied much might be because of the difficulty of extracting acknowledged authors. Unlike citations and collaborations, acknowledgments are often not indexed and are written in natural language. In this work, we exploited authors and acknowledged persons from 141,833 research articles published by open access journals (PLOS series and Scientific Reports)over the periods from 2003 to 2021 by applying core-NLP [6] and manual identification. After that, we created an acknowledgment network, in which nodes represent authors and acknowledged persons, and the links represent the acknowledgment relationships. Furthermore, we will see the relationships of acknowledgment and citation from the perspective of network science. As a result, our work contributes to provide a method for creating an acknowledgment network from text data, seek the structure of researchers' network from the perspective of acknowledgments, and the relation between acknowledgment and citation. 2 ResultsFirstly, we investigated the type of node in an acknowledgment network. Figure 1(a) illustrates the number of receiving and sending acknowledgments of authors. There exists a positive correlation between them, that is, the more an author receives acknowledgments, the more the author sends acknowledgments. On the other hand, a proportion of authors excessively received acknowledgment compared with the number of sending acknowledgments of that author and vice versa. In the following, we divide authors into the following three types: only-sending, only-receiving, and send-and-receive (S&R).Only-sending and only-receiving authors are those who only sending or receiving acknowledgments, and the remaining authors, who have both received and sent acknowledgment at least once, belong to S&R authors. Figure 1(b) illustrates the ratio of the three types of authors and sent acknowledgment within them. One striking point is that around 70% of acknowledgments are sent from only sending authors to only-receiving authors, while the largest connected components occupy more than 90% of our data. Secondly, we compare the citation of each author grouping by three types of authors. The set of citations is statistically compared by Mann–Whitney U test. As a result, only-receiving authors get cited more than only-sending authors, and one interesting fact is that when comparing only-receiving and S&R authors, the number of citations of S&R authors tends to be higher than that of only-receiving authors (Fig.2(a)). Moreover, Figure 2(b) plots the 3D scatter points which indicate the relationships between the number of sending, receiving acknowledgments, and citations which the tri-angular surface shows S&R authors. The previous studies [7, 8] indicated that there are no correlations between the number of receiving acknowledgments and citations; however, considering not only receiving counts but also sending counts of acknowledgments together, acknowledgments show a positive correlation with citations.
Federico Musciotto and Salvatore Miccichè
Optimal strategies for targeted attacks to the network of Cosa Nostra affiliates
PRESENTER: Salvatore Miccichè
ABSTRACT. The aim of the present work is to investigate the optimal strategies for targeted attacks to the Cosa Nostra affiliates network with the aim of understanding the most efficient way to dismantle such network.
The present investigation is based on the analysis of the criminal records ({\em{Certificati Penali}}) of a set of 632 affiliates to Cosa Nostra selected from a set of 125 judgements emitted by the Palermo courts from 2000 to 2014. Moreover, the Registry Office of the Palermo municipality provided us, in anonymized form, with information about the vital statistics and the list of relatives of 235 subjects condemned for mafia crimes. Starting from this data, we construct a network representation of the Cosa Nostra society by setting a link between two mafia affiliates whenever they have been sentenced in the same trial for committing the same crime.
By using a percolation-based model, we investigate the resilience properties of the network under random and targeted attacks. Random removal of network nodes results to be quite inefficient in dismantling the network. On the contrary targeted attacks where nodes are removed according to the highest values of betweenness and degree are quite effective. A strategy based on a removal of nodes starting from those who have the largest number of connections with other mafia affiliates belonging to different mafia syndicates results to have an efficiency similar to the one where nodes are removed according to their degree.
Enikő Polyák, Marcell Nagy and Roland Molontay
Towards a Better Understanding of the Characteristics of Fractal Networks
PRESENTER: Enikő Polyák
ABSTRACT. The fractal nature of complex networks has received a great deal of research interest in the last two decades. The fractality of networks has been associated with various network properties throughout the years. In this contribution, we systematically review the previous results about the relationship between various network characteristics and fractality. Moreover, we perform a comprehensive analysis of these relations on network models (including newly introduced models) and a large number of real-world networks collected from various network repositories.
John Sigbeku, Emil Saucan and Anthea Monod
Curved Markov Chain Monte Carlo for Network Learning
PRESENTER: John Sigbeku
ABSTRACT. We present a geometrically enhanced Markov chain Monte Carlo sampler for networks based on a discrete curvature measure defined on graphs. Specifically, we incorporate the concept of graph Forman curvature into sampling procedures on both the nodes and edges of a network explicitly, via the transition probability of the Markov chain, as well as implicitly, via the target stationary distribution, which gives a novel, curved Markov chain Monte Carlo approach to learning networks. We show that integrating curvature into the sampler results in faster convergence to a wide range of network statistics demonstrated in applications to both deterministic and random real-world networks.
Ardian Maulana, Hokky Situngkir and Rendra Suroso
Dynamics of Polarization and Coalition Formation in Signed Political Elite Networks
PRESENTER: Ardian Maulana
ABSTRACT. We study political elite networks within a framework of signed temporal network to investigate the dynamics of coalition formation and polarization during the 2014 Indonesian General Elections. We construct the signed network of inferred relations of agreement or disagreement between Indonesian political actors based on their opinion that is reported by news media during the election. For each tem-poral network, we detect communities by applying a community detection algo-rithm for signed networks to identify conflicting groups of political actors, and characterize the identified groups based on party attributes. We visualize the networks and measure political tensions within and between clusters to examine the dynamics of polarization over time. We find that the coalition pattern is ab-sent during the legislative election period, where political actors are more likely to group within their respective party clusters. The intensity of polarization between clusters is relatively lower than the following two periods, with a downward trend of polarization ahead of the legislative election day. The cleavage line between coalition clusters begins to form in the presidential election period and lasts into the post-election period, where the emerged pattern resembles the configuration of party coalitions in the 2014 Indonesian Presidential Election. The process of coalition formation is accompanied by an increase in the intensity of polarization between coalition clusters.
10:40-11:15Coffee Break
10:40-11:15 Session Poster P5A: [1-9] Human Behavior
Zhihao Hu, Xinwei Deng and Chris Kuhlman
Versatile Uncertainty Quantification of Contrastive Behaviors for Modeling Networked Anagram Games
PRESENTER: Zhihao Hu
ABSTRACT. In a networked anagram game, team members collectively form as many words as possible. They can share letters through a communication network in assisting their neighbors in forming words. There are contrastive behaviors of players, e.g., there can be large differences in numbers of letter requests, of replies to letter requests, and of words formed among players. Therefore, it is of great importance to understand uncertainty and variability in player behaviors in the networked anagram game. In this work, we propose a versatile uncertainty quantification (VUQ) of contrastive behaviors for modeling the networked anagram game. Specifically, the proposed methods focus on building models of game player behaviors that quantify player actions in terms of worst, average, and best performance. Moreover, we construct agent-based models (ABMs) and perform agent-based simulations (ABS) using these VUQ methods to evaluate the model building methodology and understand the impact of uncertainty. We believe that this approach is applicable to other networked games.
Manuel Marques Pita
Coherence Phase Transitions in Networked Communication Dynamics
ABSTRACT. In this work I present an Agent Based Model (ABM) to capture the dynamics of online group conversations with a focus on how different social groups coordinate the construction of coherent conversations. Agent's knowledge is modelled as a network of knowledge units, and inter-agent connectivity emerges through interactions. The model considers variables that include agent's attitude, degree of knowledge, permeability to acquire knowledge during conversation, local coherence, agent's focus. We show that this model can capture the observe coherence phase transitions across social groups. Explorations in the parameter space will be described, as well as the effects of mixing agents from different social groups in single debates.
Rodolphe Charrier and Cyrille Bertelle
Nervousness propagation within a virtual crowd
PRESENTER: Rodolphe Charrier
ABSTRACT. Extended abstract.
Rodolphe Charrier, Valentina Lanza, Damienne Provitolo, Nathalie Verdière and Edwige Dubos-Paillard
A meta-population network on geographical maps to simulate population behaviors during a catastrophic event
ABSTRACT. Extended Abstract
Emmanuel Kravitzch, Pierre-Henri Morand and Yezekael Hayel
ProPac model: opinion-action dynamics over online social networks
PRESENTER: Emmanuel Kravitzch
ABSTRACT. This extended abstract presents a model of private opinion and public action. Inspired of Discrete Choice model, it aims at capturing in the same framework both the opinion dynamics and the individual action process.
Lucía Ramirez, Maxi San Miguel and Tobias Galla
Ordering dynamics in multi-state voter models
PRESENTER: Lucía Ramirez
ABSTRACT. The Voter Model (VM) is one of the simplest interacting particle systems and it has become a paradigmatic model for the study of the dynamics of opinion formation.
We study the ordering dynamics in the multi-state voter model (MSVM)~\cite{starnini,pickering}. The system consists of $N$ interacting agents placed on the nodes of a network. Each agent can be in one of the $M$ possible opinion states ($M \leq N$). The agents interact through an imitation process in which a randomly chosen agent adopts the opinion of a randomly chosen neighbor. We are interested mainly in the time-evolution of the density of active links $\rho$.
Irene Ferri, Emanuele Cozzo, Albert Díaz-Guilera and Luce Prignano
A bounded confidence model of emotionally aroused integrate and fire oscillators.
PRESENTER: Irene Ferri
ABSTRACT. We propose an agent-based bounded confidence model for opinion dynam- ics with an interaction range regulated by an emotional arousal variable. The model includes a synchronization factor which appears to affect the final number of opinion clusters, as well as the average level of emotional arousal.
Diego Ortega, Javier Rodríguez-Laguna and Elka Koroutcheva
Segregation and universality classes in a Schelling model
PRESENTER: Diego Ortega
ABSTRACT. In this communication residential segregation is analyzed via the Schelling model, in which two types of agents attempt to optimize their situation according to certain references and tolerance levels. We consider how sudden changes in the tolerance level affect the urban structure in the closed city model, where agents can not leave the city. In this framework, sudden drops in tolerance tend to group agents into clusters whose boundary can be characterized using tools from kinetic roughening. This frontier can be categorized into the Edward-Wilkinson (EW) universality class. Likewise, the understanding of these processes and how society adapts to tolerance variations are of the utmost importance in a world where migratory movements and pro-segregational attitudes are commonplace.
Alejandro Dinkelberg, Pádraig MacCarron and Michael Quayle
Detecting opinion-based groups and polarisation on survey data
PRESENTER: Alejandro Dinkelberg
ABSTRACT. Our goal is to present a method for revealing polarisation and opinion-based groups in attitudinal surveys. We use a network-based method to explore the multidimensional opinion-based political identity structure from 2012-2020 in American National Election Studies (ANES) data, showing between- and within-group dynamics. We extract identity-related changes in the opinion space over time and confirm an ongoing trend in polarisation for a selected set of issues. The conversion of survey data into similarity-based attitude networks provides insights into opinion-based group structure and its development over time.
10:40-11:15 Session Poster P5B: [10-17] Networks Models
Gorka Zamora-López and Matthieu Gilson
Perturbation-Based Analysis: an integrative dynamical formalism for graphs to the rescue of weighted networks
PRESENTER: Gorka Zamora-López
ABSTRACT. We propose a reformulation of graph theory from a dynamical perspective. In this formalization the underlying generative model is no longer hidden, but it is explicit and tunable. This allows to define graph metrics in which link weights are built-in, and it provides the oportunity to calibrate network analysis tools by choosing generative models that are better suited for each real system under study. Thus balancing between simplicity and interpretability of results. Past efforts have employed a variety of dynamics to study complex networks by navigating on them, e.g., random walkers or routing. We envision that the formulation here proposed serves to enclose all those efforts under a common umbrella.
Víctor Muñoz and Alejandro Zamorano
Sandpiles in Networks with Variable Topology
PRESENTER: Alejandro Zamorano
ABSTRACT. Summay: We study a BTW-like sandpile model, over a network which is obtained by a random sequence of reconnections of the linear change, avoiding the existence of iso- lated nodes and ensuring energy release once an avalanche starts. The distribution of released energies is observed to depart smoothly from the linear chain case, but a clear transition can be observed at about half the maximum number of possible reconnec- tions, as evidenced by the Gini coefficient of the released energy distribution.
Furkan Atas and Mehmet Burak Akgun
Distributed Graph Generation Using Degree Correlations
PRESENTER: Furkan Atas
ABSTRACT. Graph generators are useful tools to test newly developed topological algorithms. Before algorithms run on the real systems, they are tested via synthetic graphs. However, the correctness of the test results strongly depends on the representative power of the synthetically generated graph. Since the characteristics of the data vary according to the domain to which it belongs, one of the best ways to produce random graphs by preserving characteristics is to imitate the original data. Degree Correlations based approaches imitate the original graph by replicating probability of an edge between nodes with various degrees. Our ongoing work focuses on designing scalable algorithms based on Dk series which can run on a cluster of computing nodes in a distributed fashion. This work will eventually enable the research community with open source tools that can generate multiple orders of larger synthetic graphs in a reasonable amount of time.
János Török, Gábor Tamás, Yohsuke Murase, Hang-Hyun Jo, János Kertész and Kimmo Kaski
Homophilic features of social networks from communication data
PRESENTER: János Török
ABSTRACT. We present a model based on social features to generate artificial social networks by modeling human interaction. Data about social interactions are more and more available though they are incomplete as generally links are missing as people have many choices of communication channels. This process can be modeled by a intrinsic link sampling process of the underlying social network. We define the feature overlap which is the average fraction of matching trait an ego has with its acquaintances. We show that in the ICT data this quantity shows the signs of the sampling and if the sampled model is used on the modelled data the results compare quantitatively with the empirical data.
Tomoko Sakiyama
Population Dynamics and its Instability in a Hawk-Dove Game on the Network
ABSTRACT. Evolutionary game theory reveals biological processes in populations and cooperative interactions with their neighbors. Game theory can be applied to the network evolution since social dilemma is observed in various scenarios. Recently, we investigated the link evolution using the hawk-dove game (HD) on the network system. In this model, players connected/disconnected with their neighbors based on their experiences and we found that the network structure varied depending on the time. Since a critical behavior was found in our model, we succeeded in producing a scale-free network from a random network. Here, we further investigate the population dynamics and its relation to a critical phenomenon using the above proposed model.
Gülay Canbaloğlu and Jan Treur
Context-Sensitive Mental Model Aggregation in a Second-Order Adaptive Network Model for Organisational Learning
PRESENTER: Gülay Canbaloğlu
ABSTRACT. Organisational learning processes often exploit developed individual mental models in order to obtain shared mental models for the organisation by some form of unification or aggregation. The focus of this paper is on this aggregation process, which may depend on a number of contextual factors. It is shown how a second-order adaptive network model for organisation learning can be used to model this process of aggregation of individual mental models in a context-dependent manner.
Jerry Scripps
Factoring Small World Networks
ABSTRACT. Small World networks, as defined by Watts and Strogatz, have a mixture of regular and random links. Inspired by Granovetter's definition of a weak tie, a new metric is proposed that can be used to separate a network into regular and random sub-networks. It is shown that within certain constraints, a (modified) small world network can be factored with an accuracy of 100%. The metric is shown to uncover interesting insights and factored networks can be used in downstream applications such as community finding and link prediction.
Yuki Yamagishi, Kazumi Saito, Kazuro Hirahara and Naonori Ueda
Constructing Weighted Networks of Earthquakes with Multiple-Parent Nodes Based on Correlation-Metric
PRESENTER: Yuki Yamagishi
ABSTRACT. In this paper, we address a problem of constructing weighted networks of earthquakes with multiple parent nodes, where the pairs of earthquakes with strong interaction are connected. To this end, by extending a representative conventional method based on the correlation-metric that produces an unweighted network with a single-parent node, we develop a method for constructing a network with multiple-parent nodes and assigning weight to each link by a link-weighting scheme called logarithmic-inverse-distance. In our experimental evaluation, we use an earthquake catalog that covers the whole of Japan, and select 24 major earthquakes which caused significant damage or casualties in Japan. In comparison to four different link-weighting schema, i.e., uniform, magnitude, inverse-distance, and normalized-inverse-distance, we evaluate the effectiveness of the constructed networks by our proposed method, in terms of the ranking accuracy based on the most basic centrality, i.e., weighted degree measure. As a consequence, we show that our proposed method works well, and then discuss the reasons why weighted networks with multiple-parent nodes can improve the ranking accuracy.
10:40-11:15 Session Poster P5C: [18-21] Community Structure
Soroosh Shalileh and Boris Mirkin
An Extension of K-Means for Least-Squares Community Detection in Feature-Rich Networks
PRESENTER: Boris Mirkin
ABSTRACT. We propose an extension of the celebrated K-means algorithm for community detection in feature-rich networks. Our least-squares criterion leads to a straightforward extension of the conventional batch K-means clustering method as an alternating optimization strategy for the criterion. By replacing the innate squared Euclidean distance with cosine distance we effectively tackle the so-called curse of dimensionality. We compare our proposed methods using synthetic and real-world data with state-of-the-art algorithms from the literature. The cosine distance-based version appears to be the overall winner, especially at larger datasets.
Sophie Sadler, Derek Greene and Daniel Archambault
Selecting Informative Features for Post-Hoc Community Explanation
PRESENTER: Sophie Sadler
ABSTRACT. Community finding algorithms are complex, often stochastic algorithms used to detect highly-connected groups of nodes in a graph. As with "black-box" machine learning models, these algorithms typically provide little in the way of explanation or insight into their outputs. In this research paper, inspired by recent work in explainable artificial intelligence (XAI), we look to develop post-hoc explanations for community finding, which are agnostic of the choice of algorithm. Specifically, we propose a new approach to identify features that indicate whether a set of nodes comprises a coherent community or not. We evaluate our methodology, which selects interpretable features from a longlist of candidates, in the context of three well-known community finding algorithms.
Juan Gancio and Nicolas Rubido
Community detection by resistance distance:automation and benchmark testing
PRESENTER: Juan Gancio
ABSTRACT. Heterogeneity characterises real-world networks, where nodes show a broad range of different topological features. However, nodes also tend to organise into communities -- subsets of nodes that are sparsely inter-connected but are densely intra-connected (more than the network's average connectivity). This means that nodes belonging to the same community are close to each other by some distance measure, such as the resistance distance, which is the effective distance between any pair of nodes considering all possible paths. In this work, we present automation (i.e., unsupervised) and missing accuracy tests for a recently proposed semi-supervised community detection algorithm based on the resistance distance. The accuracy testing involves quantifying our algorithm's performance in terms of recovering known synthetic communities from benchmark networks, where we present results for Girvan-Newman and Lancichinetti-Fortunato-Radicchi networks. Our findings show that our algorithm falls into the class of accurate performers.
Vincenza Carchiolo, Marco Grassia, Michele Malgeri and Giuseppe Mangioni
Analysis of the co-authorship sub-networks of Italian academic researchers
PRESENTER: Michele Malgeri
ABSTRACT. The Italian academic community is an interesting case study of emerging collaborations among people that share interest in some topics. In this paper, we select and analyze three different research areas — defined by the Italian law "academic disciplines" (SSDs) — each with different topics and interests: computer engineering, mathematics and economics. Specifically, we first collect the data of the academic researchers belonging to these SSDs from Elsevier's Scopus public database and create the co–authorship networks. Then, we study the topological characteristics and the existing communities for each network and compare them, highlighting differences and similarities.
11:15-13:00 Session Oral O7A: Network Geometry
Sebastiano Vigna
Elena Garuccio, Margherita Lalli and Diego Garlaschelli
A scale-invariant random graph model for network renormalization
PRESENTER: Margherita Lalli
ABSTRACT. Systems with lattice geometry can be renormalized by exploiting their embedding in metric space, which naturally defines the coarse-grained nodes. By contrast, complex networks defy the usual techniques, due to their small-world character and lack of explicit metric coordinates. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we illustrate a graph renormalization scheme valid for any hierarchy of coarse-grainings, thereby allowing for the definition of `block-nodes' across multiple scales. This approach reveals a necessary and specific dependence of network topology on additive hidden variables attached to nodes, plus optional dyadic factors. Renormalizable networks turn out to be consistent with a unique specification of the fitness model, while they are incompatible with preferential attachment, the configuration model or the stochastic blockmodel. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization. If the hidden variables are annealed, they lead to realistic scale-free networks with density-dependent cut-off, assortatitivy and clustering, even in the sparse regime and in absence of geometry. If they are quenched, they can guide the renormalization of real-world networks with node attributes and distance-dependence or communities. To illustrate this, we derive an accurate multiscale model of the International Trade Network applicable across hierarchically nested geographic partitions.
Gabriel Budel, Maksim Kitsak, Rodrigo Aldecoa, Konstantin Zuev and Dmitri Krioukov
Random Hyperbolic Graphs in d+1 Dimensions
PRESENTER: Gabriel Budel
ABSTRACT. We generalize random hyperbolic graphs to arbitrary dimensionality. We find the rescaling of network parameters that allows to reduce random hyperbolic graphs of arbitrary dimensionality to a single mathematical framework. Our results indicate that RHGs exhibit similar topological properties, regardless of the dimensionality of their latent hyperbolic spaces.
Riccardo Michielan and Clara Stegehuis
Cliques in geometric power-law random graphs: a phase transition for the influence of geometry
PRESENTER: Riccardo Michielan
ABSTRACT. Many real-world networks were found to be highly clustered, and contain a large amount of small cliques. We investigate the number of cliques of any size k contained in a geometric inhomogeneous random graph: a scale-free network model containing geometry. The interplay between scale-freeness and geometry ensures that connections are likely to form between either high-degree vertices, or between close by vertices. At the same time it is rare for a vertex to have a high degree, and most vertices are not close to one another. This trade-off makes cliques more likely to appear between specific vertices. We formalize this trade-off and prove that there exists a predominant type of clique in terms of the degrees and the positions of the vertices that span the clique. Moreover, we show that the asymptotic number of cliques as well as the predominant clique type undergoes a phase transition, in which only k and the degree-exponent tau are involved. Interestingly, this phase transition shows that for small values of tau, the underlying geometry of the model is irrelevant: the number of cliques scales the same as in a non-geometric network model.
Jasper van der Kolk, Marián Boguñá and Maria Ángeles Serrano
A geometry-induced topological phase transition in random graphs
PRESENTER: Jasper van der Kolk
ABSTRACT. Clustering, the tendency for neighbors of nodes to be connected, quantifies the coupling of a complex network to its underlying latent metric space. In random geometric graphs, clustering undergoes a continuous phase transition, separating a phase with finite clustering from a regime where clustering vanishes in the thermodynamic limit. We prove this geometric-to-nongeometric phase transition to be topological in nature, with atypical features such as diverging free energy and entropy as well as anomalous finite size scaling behavior. Moreover, a slow decay of clustering in the nongeometric phase implies that some real networks with relatively high levels of clustering may be better described in this regime.
Karel Devriendt, Samuel Martin-Gutierrez and Renaud Lambiotte
Variance and covariance of probability distributions on networks
PRESENTER: Samuel Martin-Gutierrez
ABSTRACT. We develop a theory to measure the variance and covariance of probability distributions defined on the nodes of a network, which takes into account the distance between nodes. Our approach generalizes the usual (co)variance to the setting of weighted networks and retains many of its intuitive and desired properties. We have applied the variance and ovariance measures to the analysis of two empirical networks of mathematical concepts built with data from Wikipedia and a collection of scientific papers. Our approach allows for a unified and intuitive treatment of the structural data (relations between concepts) and functional data (usage of concepts in papers). Since the variance and covariance are general-purpose statistical tools, these new metrics may find application in multiple fields, like neuroscience, economics or social network analysis.
Reimer Kuehn, Ofer Biham, Eytan Katzav, Haggai Bonneau and Ido Tishby
The Fate of Articulation Points and Bredges in Percolation
PRESENTER: Reimer Kuehn
ABSTRACT. We investigate the statistics of articulation points (APs) and bredges (bridge-edges) in complex networks in which bonds are randomly removed in a percolation process. APs are nodes whose removal would break the network component on which they are located into two or more disconnected components, while bredges are edges whose removal would break the network component on which they are located into two components. APs and bredges are therefore important structural elements of network architecture and crucial to maintain network integrity and functionality. Because of the heterogeneous nature of complex networks, the probability of a node to be an AP, or of an edge to be a bredge when links are randomly removed in a percolation process will not be homogeneous across the network. We therefore analyze full distributions of AP probabilities as well as bredge probabilities, using a message-passing approach to the problem, both for large single instances, and for networks in the configuration model class in the thermodynamic limit. We reveal, and are able to rationalize, a significant amount of structure in the evolution of AP and bredge probabilities in response to random bond removal. These results could be exploited in a variety of applications, including approaches to network dismantling or to vaccination and islanding strategies to prevent the spread of epidemics or of blackouts in process networks.
Bianka Kovács, Sámuel G. Balogh and Gergely Palla
Popularity-similarity optimisation model beyond two dimensions
PRESENTER: Bianka Kovács
ABSTRACT. In the field of network modelling, a non-trivial issue of high relevance is the simultaneous reproduction of different universal features that are often seen in real systems, such as sparsity, small-world property, inhomogeneous degree distribution, high average clustering coefficient or the presence of a community structure. However, e.g. hyperbolic network models, which create connections among nodes that are placed on the hyperbolic plane according to probabilities depending on the hyperbolic distances, have already been shown to be capable of generating networks that inherently possess all the above-mentioned features at the same time. Based on the success of hyperbolic models like the popularity-similarity optimisation (PSO) model of network growth and the static $\mathbb{S}^1/\mathbb{H}^2$ model, in recent years many hyperbolic embedding algorithms have been proposed that aim at arranging the nodes of a network in a hyperbolic space in a way that reflects the network topology as closely as possible. Although higher-dimensional embedding algorithms have already been proposed in the literature, the behaviour of hyperbolic network models in response to the increase in the number of dimensions of the applied hyperbolic space is not completely explored yet. The $\mathbb{S}^1/\mathbb{H}^2$ model model has recently been extended to $d>2$ dimensions. In our study, we extended the PSO model to work in a hyperbolic ball of any integer dimension $d>2$. The results show that though the clustering and the community structure weakens as the number of dimensions increases, if $d$ is just slightly larger than 2, both a high average clustering coefficient and a community structure of high modularity can still be achieved simultaneously with our $d$PSO model, indicating the relevance of low-dimensional hyperbolic spaces additionally to that of the hyperbolic plane. Furthermore, we verified both analytically and via simulations that the range of the exponent $\gamma$ of the power-law decaying tail of the degree distribution that is achievable can be extended below 2 by increasing the number of dimensions above 2.
11:15-13:00 Session Oral O7B: Network Medicine
Mauro Faccin
Piotr A. Sliwa, Gesine Reinert and Julian C. Knight
Community Detection Analysis in Multilayer COVID-19 Patient Similarity Networks
PRESENTER: Piotr A. Sliwa
ABSTRACT. Developments in experimental biology have enabled the collection of multiple molecular modalities per patient for large cohorts and exacerbated the need to develop and apply methods to integrate such datasets. Multiple ideas, such as Network Fusion, have been proposed how to use networks towards that aim. We present an alternative approach to multimodal data integration. We construct patient similarity networks based on data coming from one modality at a time, ensure that these networks are optimal with regard to their density-adjusted edge similarity and then combine these networks into a multilayer network. We then use Leiden community detection method using Modularity Vertex Partition on this multilayer network and compare the resulting communities with clinical diagnoses. We applied this multilayer network approach to a multimodal dataset containing among others information on COVID-19 and sepsis patients and healthy volunteers, to explore whether the molecular information allows us to recover clinical differences between these health and disease states with the longer-term aim of identifying unrecognised relationships and groupings. We show that using multilayer networks we can classify more patients, and, in most cases, we can refine the classification made using only one modality.
Jon Sánchez, Rion Brattig Correia, Marta Camacho-Artacho, Rosalba Lepore, Mauro M. Mattos, Luis M. Rocha and Alfonso Valencia
Multi population analysis of electronic health records reveal biases in the administration of known drug-drug interactions
PRESENTER: Rion Brattig Correia
ABSTRACT. The co-administration of drugs known to interact has a high impact on morbidity, mortality, and health economics, previously highlighted by our own work. We present a large-scale longitudinal study of the drug-drug interaction (DDI) phenomenon, focusing on age and gender biases found in drug dispensation data from three distinct health care systems. We analyze drug dispensations from population-wide electronic health records (EHR) in Blumenau (Brazil; pop. 330K), Catalonia (Spain; pop. 7.5M), and Indianapolis (USA; pop. 864K) with an observation window ranging from 1.5 to 10 years. We compute a stratified risk of DDI for several severity levels per patients' gender and age at time of dispensation. We investigate the role of polypharmacy in the observed DDI rates by building a statistical null model that shuffles drug labels while accounting for cohort specific drug availability.In addition, we build DDI networks to help explore and identify drugs involved in the DDI phenomena as well as interactions with increased gender and age risk. Our results show that in total, 149 shared DDI were found in the three populations. The risk of such DDI as patient age is also characteristically similar in all three populations. We confirm that in general women are at an increased risk of DDI---with the exception of males over 50 years-old in Indianapolis. Importantly, we find that the increased risk of DDI cannot be solely explained by polypharmacy or increased co-administration rates in the elderly. Finally, we show that proton pump inhibitor alternatives to Omeprazole can reduce the number of patients affected by known DDIs by up to 21% in Blumenau and Catalonia, exemplifying how analysis of EHR data can lead to significant reduction of DDI dispensation and its associated human and economic costs. Our work characterizes the heavy burden of DDI for health systems that are very distinct in geography, population, and policy. Although the risk of DDI increases with age, especially for patients with comorbidities, dispensation patterns point to a complex DDI phenomenon driven by culture and economics, in addition to biological factors. The lack of safer drug alternatives, particularly for chronic conditions, further overburdens health systems with patients taking a multitude of DDIs, highlighting the need for disruptive drug research.
Hilary Aroke, Natallia Katenka, Stephen Kogut and Ashley Buchanan
Network-based Analysis of Prescription Opioids Dispensing Using ERGM
PRESENTER: Hilary Aroke
ABSTRACT. The United States has been experiencing an unprecedented level of opioid overdose-related mortality due in part to excessive use of prescription opioids. Peer-driven network interventions may be beneficial. A key assumption of social network interventions is that of some members of the network act as key players and can influence the behavior of others in the network. We used opioid prescription records to create a social network of patients who use prescription opioid in the state of Rhode Island. The study population was restricted to patients on stable opioid regimens who used one source of payment and received the same opioid medication from ≥ 3 prescribers and pharmacies. An exponential random graph model (ERGM) was employed to examine the relationship between patient attributes and the likelihood of tie formation and modularity was used to assess for homophily (the tendency of individuals to associate with similar people). We used multivariable logistic regression to assess predictors of high betweenness centrality, a measure of influence within the network. 372 patients were included in the analysis; average age was 51 years; 53% were female; 57% were prescribed oxycodone, 34% were prescribed hydrocodone and 9% were prescribed buprenorphine/naloxone. After controlling for the main effects in the ERGM model, homophily was associated with age group, method of payment, number and type of opioid prescriptions filled, mean daily dose, and number of providers seen. Type of opioid and number of prescribers were identified as significant predictors of high betweenness centrality. We conclude that patients who use multiple prescribers or have a diagnosis of opioid use disorder may help promote positive health behaviors or disrupt harmful behaviors in an opioid prescription network.
Eckehard Schöll, Jakub Sawicki, Rico Berner and Thomas Löser
Modeling tumor disease and sepsis by networks of adaptively coupled phase oscillators
PRESENTER: Eckehard Schöll
ABSTRACT. In this study, we provide a dynamical systems perspective to the modelling of pathological states induced by tumors or infection. A unified disease model is established using the innate immune system as the reference point. We propose a two-layer network model for carcinogenesis and sepsis based upon the interaction of parenchymal cells (organ tissue) and immune cells via cytokines, and the co-evolutionary dynamics of parenchymal, immune cells, and cytokines. Our aim is to show that the complex cellular cooperation between parenchyma and stroma (immune layer) in the physiological and pathological case can be qualitatively and functionally described by a simple paradigmatic model of phase oscillators. By this, we explain carcinogenesis, tumor progression, and sepsis by destabilization of the healthy homeostatic state (frequency synchronized), and emergence of a pathological state (desynchronized or multifrequency cluster). The coupled dynamics of parenchymal cells (metabolism) and nonspecific immune cells (reaction of innate immune system) are represented by nodes of a duplex layer. The cytokine interaction is modeled by adaptive coupling weights between the nodes representing the immune cells (with fast adaptation time scale) and the parenchymal cells (slow adaptation time scale) and between the pairs of parenchymal and immune cells in the duplex network (fixed bidirectional coupling). Thereby, carcinogenesis, organ dysfunction in sepsis, and recurrence risk can be described in a correct functional context.
Yu Ohki, Yuichi Ikeda, Susumu Kunisawa and Yuichi Iamanaka
Healthcare Cooperation Network Constructed Using Patient Claims Data in Japan
PRESENTER: Yu Ohki
ABSTRACT. We examined the relationship between the characteristics of the medical provider network and patient recovery for a femoral neck fracture using patient claims data. We constructed a network representing the cooperation between medical providers and confirmed a negative relationship between the centrality of the network of medical providers and the duration of outpatient visits. This result indicates that patient who uses medical providers with strong healthcare cooperation have a shorter time to recover from fracture. In addition, the presentation discusses the impact of isolation of medical providers from the healthcare system on the quality of healthcare provision and the comparison of characteristics of the healthcare system in each geographic region using community analysis of the network.
Prashant Sanjel and John Matta
Inferred Networks and the Social Determinants of Health
PRESENTER: Prashant Sanjel
ABSTRACT. This paper explores the social determinants of health through a network science based approach to analyzing the Latino MSM Community Involvement (LMSM-CI) dataset. Data are clustered to determine identifying characteristics of groups of participants in 3 categories: high self esteem, susceptibility to alcohol abuse, and HIV positive status. A question arises as to the best methodology for inferring a graph from the data, as well as for clustering and analyzing the network. To that end we use 4 different graph inference methods: inverse covariance selection (Glasso), neighborhood selection (MB), Sparse Correlations for Compositional data (SparCC) and the traditional k-Nearest Neighbors (kNN). For each inference we test 4 different clustering methods: Louvain, Leiden, NBR-Clust with VAT, and NBR-Clust with integrity. Surprisingly, the Glasso and MB inference methods produce better clusterings than kNN, as determined by a suite of internal evaluation measures. The most promising clusterings are visualized and their properties are analyzed.
Sarel Cohen, Moshik Hershcovitch, Martin Taraz, Otto Kissig, Andrew Wood, Daniel Waddington, Peter Chin and Tobias Friedrich
Drug Repurposing using Link Prediction on Knowledge Graphs with Applications to Non-Volatile Memory
PRESENTER: Sarel Cohen
ABSTRACT. The active global SARS-CoV-2 pandemic caused more than 167 million cases and 3.4 million deaths worldwide. As mentioned in a recent research paper by AstraZeneca and Cambridge [Ye et al. 2021], the development of completely new drugs for such a novel disease is a challenging, time intensive process and despite researchers around the world working on this task, no effective treatments have been developed yet. This emphasizes the importance of \emph{drug repurposing}, where treatments found among existing drugs meant for different diseases. A common approach to this is based on \emph{knowledge graphs}, that condense relationships between entities like drugs, diseases and genes. Graph neural networks (GNNs) can then be used for the task at hand by predicting links in such knowledge graphs. Expanding on state-of-the-art GNN research, Doshi et al. originally presented the model Dr-COVID.
We further extend their work using additional output interpretation strategies. The best aggregation strategy derives a top-100 ranking of candidate drugs, 32 of which currently being in COVID-19-related clinical trials. Moreover, we present an alternative application for the model, the generation of additional candidates based on a given pre-selection of drug candidates using collaborative filtering. In addition, we improved the implementation of the model of Dr-COVID by significantly shortening the inference and pre-processing time by exploiting data-parallelism.
Additionally, we propose a new approach to leverage the use of high-capacity Non-Volatile Memory for aggregate drug ranking. We show initial promising results that processing large datasets is faster with persistent memory than running with the commonly used hardware of DRAM and NVMe SSD.
11:15-13:00 Session Oral O7C: Urban Systems & Networks
Inho Hong
Daniel Rhoads, Albert Solé-Ribalta, Marta C. González and Javier Borge-Holthoefer
A sustainable strategy for Open Streets in (post)pandemic cities
PRESENTER: Javier Borge-Holthoefer
ABSTRACT. Cities world-wide have taken the opportunity presented by the COVID-19 pandemic to improve and expand pedestrian infrastructure, providing residents with a sense of relief and pursuing long-standing goals to decrease automobile dependence and increase walkability. So far, due to a scarcity of data and methodological shortcomings, these efforts have lacked the system-level view of treating sidewalks as a network. Here, we leverage sidewalk data from ten cities in three continents, to first analyse the distribution of sidewalk and roadbed geometries, and find that cities present an unbalanced distribution of public space, favouring automobiles at the expense of pedestrians. Next, we connect these geometries to build a sidewalk network --adjacent, but irreducible to the road network. Finally, we compare a no-intervention scenario with a shared-effort heuristic, in relation to the performance of sidewalk infrastructures to guarantee physical distancing. The heuristic prevents the sidewalk connectivity breakdown, while preserving the road network's functionality.
Nazli Barcin Dogan and Alfonso Mejia
Supply Chain Complexity of US Cities
PRESENTER: Nazli Barcin Dogan
ABSTRACT. Our hyperconnected world is characterized by complex supply networks that facilitate the flow of products across the entire globe. However, supply flows intensify in cities, since cities concentrate people, resources, and economic activity. This intensification of supply flows and social interactions makes cities engines of economic growth and innovation, but at the same time it may increase cities' exposure to exogenous supply chain shocks. A supply chain shock is a sudden reduction in the inflow of a resource or product to a city. Through the propagation of a supply chain shock from one location to another, supply chains can increase the risk and vulnerability of a city to disruptions occurring elsewhere in the network system, which may ultimately have a destabilizing effect on city functioning and life. In this study, we derive a network-based index of supply chain complexity to characterize the spatial structure of a city's supply network. This supply-chain complexity index (SCI) is data-driven, grounded in economic complexity theory, and practical to implement using available datasets. We use commodity flow networks to represent supply flows in the contiguous United States, including international connections. Results of this study that supply chain complexity may benefit cities, since the average intensity of supply chain shock and the probability of experiencing a supply chain shock declines as the supply chain complexity of cities rises. Here, analogous to the beneficial complexity-diversity relationship seen in different ecosystems, we find that supply chain complexity can contribute to making a city more resilient to supply chain shocks. The realization of these benefits, however, will hinge on having an adequate supply chain governance structure and processes. Supply chain disruptions are anticipated to rise in the future due to global political, economic, health, and environmental crises. Nature has already shown that resilience principles work, it is now up to us to apply these lessons for the benefit of society.
Francisco Prieto-Castrillo, Rosa M. Benito and Javier Borondo
Understanding Imbalance Mechanisms in Shared Mobility Systems
PRESENTER: Francisco Prieto-Castrillo
ABSTRACT. We explore numerically and analytically how a fleet of vehicles moving through a stations network becomes unbalanced. Framing the system in terms of a mathematical simplex subjected to stochastic flows allows us to understand system's failure rigorously. This allows to find the effect of self-journeys in system's stability. With a birth-death process approach we find analytical upper bounds for random walk and we monitor how the system collapses by super-diffusing under different randomisation conditions.
Ashis Kumar Pal, Nishant Yadav and Auroop R. Ganguly
Network Science-Based Resilience Analysis of Urban Rail Transportation Systems
PRESENTER: Auroop R. Ganguly
ABSTRACT. Critical urban lifeline infrastructure networks (CULINs), such as transportation systems, are essential to maintain vital urban societal functions. 68% of the world population is projected to live in urban areas by 2050, elevating flood risk to people's lives, economy, and critical infrastructure systems, including transport, power, and escalating pressure on already overburdened CULINs. Traditional network science-based resilience studies have mainly focused on topological network properties while ignoring intrinsic dynamic flow effects. However, for real-world infrastructure networks, the removal of nodes (topological analysis) can have different consequences when the network dynamics are also considered. In this study, we analyze the performance of eight major urban transportation systems (UTS) under different types of disruptions, including a simulated flooding failure; and compare their resilience properties under topology-only and flow-based paradigms. The results point to the complementary nature of the two paradigms where a UTS network can be vulnerable in framework while relatively robust under another. Further, under certain conditions, a single point of flooding failure can cause network-wide loss of functionality. The insights generated is expected to help stakeholders to execute quantifiable resilience analysis and develop mitigation strategies.
Aaron Bramson
Neighborhood Discovery via Network Community Structure
ABSTRACT. Compared to social and information networks, the geospatial characteristics of transportation networks make them structurally constrained. Although road, flight, train, and other such networks have been analyzed using social network analysis methods, the results typically fail to capture useful characteristics or make informative comparisons. In the case of road networks, natural constraints on the edge distribution weaken the ability of standard community detection algorithms to find intuitively separable neighborhoods. We show that by adding edge weights based on the similarity of localized subgraph features we can apply modularity-based community detection algorithms to uncover intuitively distinct neighborhoods. The use of local network characteristics allow the feature analysis to be completed in linear time, thus making the approach expandable to very large networks. We demonstrate this technique with an application to central Tokyo.
Indaco Biazzo
CityChrone: an interactive platform for transport network analysis and planning in urban systems
ABSTRACT. Urban systems studies in the last decades have greatly benefited from the digital revolution and the accumulation of a massive amount of data. Extracting useful information from these data calls for new and innovative theoretical and computational approaches. This work presents an open-source, modular, and scalable platform for urban planning and transports network analysis, the CityChrone [citychrone.org]. The platform shows, on interactive maps, measures of performances of public transport in cities. The measures are based on the computation of the travel time distance between a large set of points. Thanks to the high efficiency of the routing algorithm developed, the platform allows users to create new public transports networks and showing the effect on mobility in a small amount of time. A preliminary analysis of the user-generated scenarios is presented. All the source code of the CityChrone platform is open-source, and we employ only open data to ensure the reproducibility of results.
Unchitta Kan and Eduardo Lopez
Layered Hodge Decomposition for Urban Transit Networks
PRESENTER: Unchitta Kan
ABSTRACT. Modeling the amount of passenger flow along any given line segment of an urban transit network such as the London Underground is a challenging problem due to the complexity of the system. In this paper, we embark on a characterization of these flows on the basis of a combination of (1) a layered decomposition of the origin-destination matrix, and (2) the Hodge decomposition, a discrete algebraic topology technique that partitions flows into gradient, solenoidal, and harmonic components. We apply our method to data from the London Underground. We find that the layered decomposition estimates the contribution of flow of each origin-destination pair on each network link, and that the solenoidal and harmonic flows are described by simple equations that bypass the need for complicated numerical solutions. This reduces much of the solution of the flow problem to determining gradient flows (i.e., flows that would occur if the transit system were a hydraulic or electric circuit). Our exploratory analysis suggests that it may be feasible to develop solution methods for the transit flow problem with a complexity equivalent to the solution of a hydraulic or electric circuit.
13:00-14:15Lunch Break
14:15-15:45 Session Oral O8A: Community Structure
Alexandre Bovet
Mauro Faccin, Michael Schaub and Jean-Charles Delvenne
Auto-Information State Aggregations
PRESENTER: Mauro Faccin
ABSTRACT. Model reduction is one of the most used tools to characterize real-world complex systems. A large realistic model is approximated by a simpler model on a smaller state space, capturing what is considered by the user as the most important features of the larger model. For instance, time-separation techniques collapse fast modes to reduce the number of variables needed to accurately describe the system in the longer time scales. In this work we introduce a new information-theoretic criterion, called "autoinfor- mation", that aggregates states of a Markov chain while providing a reduced model as Markovian (small memory of the past) and as predictable (small level of noise) as possible. This approach consists in finding the partition that maximizes the mutual information between states in the aggregated space (as opposed to covariance in Stability and Modularity). To demonstrate the strengths of autoinformation maximization, we introduce a new family of networks together with real world examples and compare the outcome to existing and widely accepted alternative approaches.
Lotte Weedage, Nelly Litvak and Clara Stegehuis
Locating clusters in large networks with HyperLogLog counters
PRESENTER: Lotte Weedage
ABSTRACT. In this talk, we introduce a new method to locate highly connected clusters in a network. Our proposed approach adapts the HyperBall algorithm to localize regions with a high density of small subgraph patterns in large graphs in a memory-efficient manner. We use this method to evaluate three measures of subgraph connectivity: conductance, the number of triangles, and transitivity. We demonstrate that our algorithm, applied to these measures, helps to identify clustered regions in graphs, and provides good seed sets for community detection algorithms such as PageRank-Nibble. We analytically obtain the performance guarantees of our new algorithms and demonstrate their effectiveness in a series of numerical experiments on synthetic and real-world networks.
Georgia Baltsou and Konstantinos Tsichlas
Dynamic Community Detection with Anchors
PRESENTER: Georgia Baltsou
ABSTRACT. Many real-world networks are highly dynamic since both new relations (edges) and entities (nodes) may appear, while others might disappear. An important aspect of dynamic networks is that as they evolve, their communities may change, i.e., new communities appear, existing communities disappear, grow or shrink. In many cases, we are not interested in a global partitioning of the network but in looking at the evolution of a particular community or of the community that an important node belongs. However, it is difficult to keep track of the evolving communities because of the drifting problem, where a community might shift to a completely different one. Our goal is to propose a general framework for detecting the community that contains a set of nodes of particular importance, termed anchors, as well as its evolution over time. Our framework circumvents the identity problem by letting the anchors define partially or completely the core of the corresponding community.
Pegah Hozhabrierdi and Sucheta Soundarajan
CoVerD: Community-based Vertex Defense against Crawling Adversaries
PRESENTER: Pegah Hozhabrierdi
ABSTRACT. The problem of hiding a node inside of a network in the presence of an unauthorized crawler is shown to be NP-complete. The available heuristics tackle this problem from mainly two perspectives: (1) the local immediate neighborhood of the target node (local perturbation models) and (2) the global structure of the graph (global perturbation models). While the objective of both is similar (i.e., decreasing the centrality of the target node), they vary substantially in their performance and efficiency; the global measures are computationally inefficient in the real-world scenarios, and the local perturbation methods deal with the problem of constrained performance. In this study, we propose a community-based heuristic, \textit{CoVerD}, that retains both the computational efficiency of local methods and the superior performance of global methods in minimizing the target's closeness centrality. Our experiments on five real-world networks show a significant increase in performance by using \textit{CoVerD} against both BFS and DFS crawling attacks. In some instances, our algorithm successfully increased the crawler's budget by $3$ and $10$ times compared to the next best-performing benchmark. The results of this study show the importance of the local community structure in preserving the privacy of the nodes in a network, and pave a promising path for designing scalable and effective network protection models.
Paolo Boldi, Flavio Furia and Sebastiano Vigna
Spectral Rank Monotonicity on Undirected Networks
PRESENTER: Sebastiano Vigna
ABSTRACT. We study the problem of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in the case of undirected networks. Score monotonicity means that adding an edge increases the score at both ends of the edge. Rank monotonicity means that adding an edge improves the relative position of both ends of the edge with respect to the remaining nodes. It is known that most spectral rankings are both score and rank monotone on directed, strongly connected graph. We show that, surprisingly, the situation is very different for undirected graphs, and in particular that PageRank is neither score nor rank monotone.
Vladimir Ivashkin and Pavel Chebotarev
Dissecting graph measure performance for node clustering in LFR parameter space
PRESENTER: Vladimir Ivashkin
ABSTRACT. Graph measures that express closeness or distance between nodes can be employed for graph node clustering using metric clustering algorithms. There are numerous measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR graph generator, we create a dataset of 9275 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for each considered measure. Based on this, we determine the best measure for each area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to recommend a particular measure to use for clustering.
14:15-15:45 Session Oral O8B: Networks in Finance & Economics
Cinzia Pinello, Michele Tumminello and Arabella Mocciaro Li Destri
A NETWORK PERSPECTIVE ON CO-BRANDING CAMPAIGNS: EVIDENCE FROM THE FASHION INDUSTRY
PRESENTER: Cinzia Pinello
ABSTRACT. During the last years, co-branding strategies have attracted significant interest in marketing research. Previous studies have analyzed this phenomenon by focusing on dyadic relationships between brands. Instead, this study adopts a comprehensive perspective and uses a network approach to understand the influence of companies' co-branding portfolios of previous alliances on the partnership formation process. By using concepts and methods derived from Signaling Theory and Network Theory, we demonstrate that the brand portfolio of alliances, captured through the network structure that maps the relationships between brands, significantly influences the partner selection process. Indeed we propose a probabilistic model of partnership formation solely based on local network metrics and demonstrate its effectiveness in predicting future alliances. Finally, the empirical analysis of the network of cobranding campaigns allows us to identify several logics underlying co-branding partnership formation, most of which are driven by company logics, rather than the consumer oriented logics typically studied in the literature.
Leonardo Niccolò Ialongo, Camille de Valk, Emiliano Marchese, Fabian Jansen, Hicham Zmarrou, Tiziano Squartini and Diego Garlaschelli
Reconstructing firm-level interactions: the Dutch input-output network
PRESENTER: Leonardo Niccolò Ialongo
ABSTRACT. Information on input-output relationships is publicly available only at aggregate industry level. For those applications where it is important to know the structure of the network at firm level it is necessary to use an appropriate reconstruction technique. In this work, we propose a fitness induced configuration model that based on knowledge of the total flows by sector for each firm as well as the density of the original graph is able to generate a probability distribution over all networks which preserves important structural properties of the original network. We test the quality of our methodology on two complementary datasets of Dutch firms finding good support for our technique.
Christian Diem, András Borsos, Tobias Reisch, Janos Kertesz and Stefan Thurner
The necessity of firm-level modelling of shock spreading in supply chain networks
PRESENTER: Christian Diem
ABSTRACT. Models for the spreading of shocks in production networks are one of the key tools to assess the economic and consequently societal effects caused by large crises events, such as natural disasters [1], or the COVID-19 pandemic [2]. These models simulate how the initial shocks ---stemming from such crises scenarios--- spread from the directly affected parts of the economic network to the overall system. The economic networks underlying these models are usually sector level Input-Output tables, that are strongly aggregated representations of highly complex firm level supply networks. However, if firms within given industry sectors are linked very heterogeneously to firms from other sectors, the aggregated sector level network will lead to false shock spreading dynamics for crises assessment models. In fact initial shocks ---triggering the shock spreading--- that would produce vastly different cascades on the firm level network, will be indistinguishable on the sector level network.
Based on the firm-level production network of Hungary, containing more than 240,000 firms and more than a million links, we show that firms within given industry sectors exhibit vastly heterogeneous interlinking in the production network. By using a firm-level shock propagation model tailored for production networks [3], we show that crises scenarios with the same initial shock size with respect to the affected output of each sector, but affecting different companies within the sectors, lead to substantially different shock cascades. This implies that highly aggregated sector level production networks lead to large losses in information when used for the analysis of economic shock spreading.
See PDF for the full extended Abstract.
1. S. Hallegatte, C. Green, R.J. Nicholls, J. Corfee-Morlot, Nat. Clim. Change 3, (2013) 802 2. A. Pichler, M. Pangallo, M. d. Rio-Chanona, F. Lafond, D. Farmer, SSRN3788494 (2021) 3. C. Diem, A. Borsos, T. Reisch, J. Kertész, S. Thurner, arXiv:2104.07260 (2021)
Andras Borsos, Christian Diem, Tobias Reisch, Janos Kertesz and Stefan Thurner
Quantifying firm-level economic systemic risk from nation-wide supply networks
PRESENTER: Andras Borsos
ABSTRACT. Crises like COVID-19 or the Japanese earthquake in 2011 exposed the fragility of corporate supply networks. The production of goods and services is a highly interdependent process and can be severely impacted by the default of critical suppliers or customers. While knowing the impact of individual companies on national economies is a prerequisite for efficient risk management, the quantitative assessment of the involved economic systemic risks (ESR) is hitherto practically non-existent, mainly because of a lack of fine-grained data in combination with coherent methods. Based on a unique value added tax dataset we derive the detailed production network of an entire country and present a novel approach for computing the ESR of all individual firms. We demonstrate that a tiny fraction (0.035%) of companies has extraordinarily high systemic risk impacting about 23% of the national economic production should any of them default. Firm size alone cannot explain the ESR of individual companies; their position in the production networks does matter substantially. If companies are ranked according to their economic systemic risk index (ESRI), firms with a rank above a characteristic value have very similar ESRI values, while for the rest the rank distribution of ESRI decays slowly as a power-law; 99.8% of all companies have an impact on less than 1% of the economy. We show that the assessment of ESR is impossible with aggregate data as used in traditional Input-Output Economics. We discuss how simple policies of introducing supply chain redundancies can reduce ESR of some extremely risky companies.
Luca Mungo, François Lafond and J. Doyne Farmer
Reconstructing production networksusing machine learning
PRESENTER: Luca Mungo
ABSTRACT. The vulnerability of supply chains and their role in the propagation of shocks has been highlighted multiple times in recent years, including by the recent pandemic. However, while the importance of micro data is increasingly recognised, data at the firm-to-firm level remains scarcely available. In this study, we formulate supply chain networks' reconstruction as a link prediction problem and tackle it using machine learning, specifically Gradient Boosting. We test our approach on three different supply chain datasets and show that it works very well, and outperforms three benchmarks. An analysis of features' importance suggests that the key data underlying our predictions are firms' industry, location, and size. To evaluate the feasibility of reconstructing a network when no production network data is available at all, we attempt to predict a dataset using a model trained on another dataset, showing that the model's performance deteriorates substantially, while still beating the random benchmark.
Loredana Bellantuono, Alfonso Monaco, Sabina Tangaro, Nicola Amoroso, Vincenzo Aquaro and Roberto Bellotti
An Equity-Oriented Rethink Of Global Rankings With Complex Networks Mapping Development
PRESENTER: Loredana Bellantuono
ABSTRACT. In this work, we propose a methodology for an equity-oriented evaluation of a country's performances in international rankings, that takes into account the multifaceted aspects of its development condition. In particular, we adopt the machinery of complex network theory to partition world countries in communities characterized by a homogeneous development level. The network model, in which each node corresponds to one of the 193 UN Member States, is based on the similarity of World Development Indicator (WDI) values for different states. The communities identified from the network analysis provide not only a tool to group countries by development similarity, but also a way to reinterpret their positions in international rankings. After a quantitative check of the correlation between community membership and score in a given ranking, we identify countries whose performance goes beyond the expectations based on their development status, and countries that have the potential to reach, by increasing their efforts, the score of their community peers. We analyze the cases of five different rankings, focusing on different domains. Stemming from the field of economic complexity, this idea meets a crucial need for governance, overcoming state-of-the art rating systems, in which the development status is synthesized by a small number of aggregated indicators. Complex network theory is used here to elaborate a pipeline providing a fair, transparent and reproducible rating system, that incorporates complex information on development, unveiling nontrivial similarities between countries and setting improved paradigms in performance assessment.
14:15-15:45 Session Oral O8C: Resilience, Synchronization & Control
I. Leyva
Marco Grassia, Manlio De Domenico and Giuseppe Mangioni
Machine learning dismantling and early-warning signals of disintegration in complex systems
PRESENTER: Marco Grassia
ABSTRACT. Please, see the attached pdf file.
Masaki Chujyo and Yukio Hayashi
Improvement of the robustness against attacks in continuously varying degree distributions
PRESENTER: Masaki Chujyo
ABSTRACT. To realize a robust system against intentional attacks is an important problem for our modern society. In particular, scale-free networks are extremely vulnerable to intentional attacks, so a network structure with higher robustness of connectivity against attacks is required. In this work, we aim to clarify the effect of the variance of degree distribution on the robustness of connectivity against attacks. We numerically investigated the robustness by continuously varying degree distributions from a power-law to an exponential. We found that the smaller variances of degree distributions lead to higher robustness at least in this range. In addition, we investigate a relation between the robustness and the rate of Feedback Vertex Set (FVS) on varying degree distributions. Our result shows that the robustness becomes higher as the variance is smaller, and that rate of FVS is also larger. It suggests that enhancing loops is important for improving robustness.
Mahdi Moshiri and Farshad Safaei
Retrieval of redundant hyperlinks after attack based on hyperbolic geometry of web Complex Networks
PRESENTER: Mahdi Moshiri
ABSTRACT. The Internet and the Web can be described as huge networks of connected computers, connected web pages, or connected users. Analyzing link retrieval methods on the Internet and the Web as examples of complex networks is of particular importance. The recovery of complex networks is an important issue that has been extensively used in various fields. Much work has been done to measure and improve the stability of complex networks during attacks. Recently, many studies have focused on the network recovery strategies after the attack. Predicting the appropriate redundant links in a way that the network can be recovered at the lowest cost and fastest time after attacks or interruptions will be critical in a disaster. In addition, real-world networks such as the World Wide Web are no exception, and many attacks are made on hyperlinks between web pages, and the issue of predicting redundant hyperlinks on this World Wide Web is also very important. In this paper, different kinds of attack strategies are provided and some retrieval strategies based on link prediction methods are proposed to recover the hyperlinks after failure or attack. Besides that, a new link prediction method based on the hyperbolic geometry of the complex network is proposed to retrieve redundant hyperlinks and the numerical simulation reveals its superiority that the state-of-the-art algorithms in recovering the attacked hyperlinks especially in the case of attacks based on edge betweenness strategy.
Zhongqi Cai, Enrico Gerding and Markus Brede
Accelerating Opponent Strategy Inference for Voting Dynamics on Complex Networks
PRESENTER: Zhongqi Cai
ABSTRACT. In this paper, we study the problem of opponent strategy inference from observations of information diffusion in voting dynamics on complex networks. We demonstrate that, by deploying resources of an active controller, it is possible to influence the information dynamics in such a way that opponent strategies can be more easily uncovered. To this end, we use the framework of maximum likelihood estimation and the Fisher information to construct confidence intervals for opponent strategy estimates. We then design heuristics for optimally deploying resources with the aim of minimizing the variance of estimates. In the first part of the paper, we focus on inferring an opponent strategy at a single node. Here, we derive optimal resource allocations, finding that, for low controller budget, resources should be focused on the inferred node and, for large budget, on the inferred nodes' neighbours. In the second part, we extend the setting to inferring opponent strategies over the entire network. We find that opponents are the harder to detect the more heterogeneous networks are, even with optimal targeting.
Jisha Mariyam John and Divya Sindhu Lekha
Need for a realistic measure of attack severity in centrality based node attack strategies
PRESENTER: Jisha Mariyam John
ABSTRACT. Complex networks are robust to random failures; but not always to targeted attacks. The resilience of complex networks towards different node targeted attacks are studied immensely in the literature. Many node attack strategies were also proposed, and their efficiency was compared. However, in each of these proposals, the scientists used different measures of efficiency. So, it doesn't seem easy to compare them and choose the one most suitable for the system under examination. Here, we review the main results from the literature on centrality-based node attack strategies. Our focus is only on the works on undirected and unweighted networks. We want to highlight the necessity of a more realistic measure of attack efficiency.
Po-An Chen, Ya-Wen Cheng and Yao-Wei Tseng
Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs
PRESENTER: Po-An Chen
ABSTRACT. Gionis et al. have already proposed the greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we want to adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, the interactive influence between nodes will not cycle, but would spread outwards. Based on such insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximate solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.
15:45-16:20Coffee Break & Online Session for Onsite Presenters of Poster Session P5 A-B-C
16:20-17:00 Session Speaker S6: Dirk Helbing - How Networks Can Change Everything for Better or for Worse
Albert Solé Ribalta
Dirk Helbing
How Networks Can Change Everything for Better or for Worse
ABSTRACT. Complexity science has been studying the result of dynamical and network interactions in multi-agent systems for a long time. This work has revealed many intriguing relationships between structure, function, and dynamics. By now, it is known that the interaction mechanisms and the network structure can decide about success or failure, disease or disaster. I will present examples from logistics to economics, from game theory to society, and from traffic light control to pandemics to illustrate how changing the network structure and interactions can make all the difference between paradise and hell.
17:00-18:15 Session Oral O9A: Diffusion & Epidemics
Giulia Cencetti
Meher Chaitanya Pindiprolu and Ulrik Brandes
Hardness Results for Seeding Complex Contagion with Neighborhoods
PRESENTER: Meher Chaitanya Pindiprolu
ABSTRACT. Identifying the minimum set of initiators in fixed threshold complex contagions to bring about behavioral change in a network is a well-known problem that has been studied under different names such as influence maximization or Target Set Selection (TSS). It is known to be hard to approximate within a polylogarithmic factor.
Recently, Guilbeault and Centola (Nature Communications, 2021) employed a novel seeding strategy in which seed nodes are included together with all of their neighbors. Referring to this variant as Neighborhood-TSS (N-TSS), we provide hardness and inapproximability results for identifying minimum-cardinality seed sets. In addition, we lower a Strong Exponential Time Hypothesis (SETH)-based lower bound on the running time for the cardinality-k TSS with uniform threshold k from k=3 to k=2.
Trevor Kent, Nolan Phillips, Ian McCulloh, Viveca Pavon-Harr and Heather Patsolic
Microscopic Markov Chain Approach for Measuring Mobility Driven SARS-CoV-2 Transmission
PRESENTER: Trevor Kent
ABSTRACT. After more than a year of non-pharmaceutical interventions, such as, lock-downs and masks, questions remain on how effective these interventions were and could have been. The vast differences in the enforcement of and adherence to policies adds complexity to a problem already surrounded with significant uncertainty. This necessitates a model of disease transmission that can account for these spatial differences in interventions and compliance. In order to measure and predict the spread of disease under various intervention scenarios, we propose a Microscopic Markov Chain Approach (MMCA) in which spatial units each follow their own Markov process for the state of disease but are also connected through an underlying mobility matrix. Cuebiq, an offline intelligence and measurement company, provides aggregated, anonymized cell-phone mobility data which reveal how population behaviors have evolved over the course of the pandemic. These data are leveraged to infer mobility patterns across regions and contact patterns within those regions. The data enables the estimation of a baseline for how the pandemic spread under the true ground conditions, so that we can analyze how different shifts in mobility affect the spread of the disease. We demonstrate the efficacy of the model through a case study of spring break and it's impact on how the infection spread in Florida during the spring of 2020, at the onset of the pandemic.
Eszter Bokányi, Martin Novák, Ákos Jakobi and Balazs Lengyel
Urban hierarchy and spatial diffusion over the innovation life cycle
PRESENTER: Eszter Bokányi
ABSTRACT. Successful innovations achieve large geographical coverage by spreading across settlements and distances. For decades, spatial diffusion has been argued to take place along the urban hierarchy. Yet, the role of geographical distance was difficult to identify in hierarchical diffusion due to missing data on spreading events. In this paper, we exploit spatial patterns of individual invitations sent from registered users to new users over the entire life cycle of a social media platform. We demonstrate that hierarchical diffusion overlaps with diffusion to close distances and these factors co-evolve over the life cycle. Therefore, we disentangle them in a regression framework that estimates the yearly number of invitations sent between pairs of towns. We confirm that hierarchical diffusion prevails initially across large towns only but emerges in the full spectrum of settlements in the middle of the life cycle when adoption accelerates. Unlike in previous gravity estimations, we find that after an intensifying role of distance in the middle of the life cycle a surprisingly weak distance effect characterizes the last years of diffusion. Our results stress the dominance of urban hierarchy in spatial diffusion and inform future predictions of innovation adoption at local scales.
Alessandro Celestini, Francesca Colaiori, Stefano Guarino, Enrico Mastrostefano and Lena Rebecca Zastrow
Epidemics in a Synthetic Urban Population with Multiple Levels of Mixing
PRESENTER: Stefano Guarino
ABSTRACT. The prediction and control of infectious diseases have an enormous impact on public health, the economy and society. Network--based epidemic models are extensively used to account for heterogeneous contact patterns, that include recurrent contacts and may explain hierarchical spread and other empirical findings. In this paper, we use census and survey data to reconstruct a geo--referenced and age--stratified synthetic urban population connected by a network of stable social relations. We consider three classes of contacts: while fortuitous contacts may occur between any two agents, daily and frequent contacts are bound to the edges of two different layers of the inferred social network. Through extensive simulations set in a typical medium--sized Italian city, we characterize the epidemic spread at the urban scale, emphasizing how the speed, pervasiveness and predictability of the diffusion process are related to the socio--demographic and geographic features of the host population.
Van Sy Mai and Richard La
Story of Two Populations in Epidemics: Is Every Infection Counted?
PRESENTER: Richard La
ABSTRACT. Many previous studies on epidemic processes assume that most infected nodes that contribute to the spread of infection can be identified and accounted for. But, in some cases, this assumption may be invalid and many infection cases may go undetected. For example, the operators of subsystems in complex systems may be unaware that their systems are compromised by malware or a virus, which may go undetected for a long period. Similarly, an infectious disease can cause widely varying symptoms and some infected individuals may exhibit little to no symptoms. In these scenarios, it would be difficult to identify all infected systems or individuals, which can play a critical role in spreading the infection by malware, virus or disease. For this reason, it is of interest to devise a means of quickly determining the presence of such undetected infection cases in a network. We propose a simple optimization-based approach that can be used to determine whether or not a significant fraction of infection cases are undetected and thus are missing in reported statistics. We present numerical results obtained from a case study using publicly available COVID-19 data from four countries.
17:00-18:15 Session Oral O9B: Information Spreading in Social Media
Fariba Karimi
Wilson Ceron, Mathias-Felipe de-Lima-Santos and Marcos Gonçalves Quiles
Against the Democracy: The Power of Coordinator Inauthentic Behavior Pushing Anti-Democratic Narratives on Twitter amidst COVID-19 pandemic
PRESENTER: Marcos Gonçalves Quiles
ABSTRACT. Social media platforms enabled users to participate in online social networking, by creating and sharing content. On the other hand, users with malicious intent used these platforms to promote hate speech and antidemocratic tactics. In Brazil, several anti-democratic narratives became popular on Facebook, Instagram, and Twitter, such as the restoration of dictatorship, the end of the Supreme Court, the requests for military intervention, among others. These rhetorics present a major risk for democracy and jeopardize fundamental rights. To understand the dissemination of this discussion on Twitter, this study analyzes 1.7 million tweets that used terms associated with anti-democratic content. Findings suggest that these narratives are spread by accounts that presents traces of coordinated inauthentic behavior, that is, these tweets were published by automated accounts. In addition, six major clusters of anti-democratic narratives could be found, which resembles echo chambers promoting rethrotic against the democracy. Our study concludes by arguing that if Twitter takes action against a small number of accounts that spread most anti-democratic content, there is a great chance that these echo chambers can be broken.
Seema Nagar, Sameer Gupta, Bahushruth Cs, Ferdous Barbhuiya and Kuntal Dey
Hate Speech Detection on Social Media Using Graph Convolutional Networks
PRESENTER: Seema Nagar
ABSTRACT. Detection of hateful content on Twitter has become the need of the hour. Hate detection is challenging primarily due to the subjective definition of hateful. In the absence of context, text content alone is often not sufficient to detect hate. In this paper, we propose a framework that combines content with context, to detect hate. The framework takes into account (a) textual features of the content and (b) unified features of the author to detect hateful content. We use a Variational Graph Auto-encoder (VGAE) to jointly learn the unified features of authors using a social network, content produced by the authors, and their profile information. To accommodate emerging and future language models, we develop a flexible framework that incorporates any text encoder as a plug-in to obtain the textual features of the content. We empirically demonstrate the performance and utility of the framework on two diverse datasets from Twitter.
Richard Kuzma, Iain Cruickshank and Kathleen Carley
Influencing the Influencers: Evaluating Person-to-Person Influence on Social Networks Using Granger Causality
PRESENTER: Richard Kuzma
ABSTRACT. We introduce a novel method for analyzing person-to-person content influence on Twitter. Using an Ego-Alter framework and Granger Causality, we examine President Donald Trump (the Ego) and the people he retweets (Alters) as a case study. We find that each alter has a different scope of influence across multiple topics, different magnitude of influence on a given topic, and the magnitude of a single Alter's influence can vary across topics. This work is novel in its focus on person-to-person influence and content-based influence. Its impact is two-fold: (1)identifying "canaries in the coal mine" who could be observed by misinformation researchers or platforms to identify misinformation narratives before super-influencers spread them to large audiences, and (2) enabling digital marketing targeted toward upstream Alters of super-influencers.
Valeria Fionda and Giuseppe Pirrò
Community Deception in Networks: Where We Are and Where We Should Go
PRESENTER: Giuseppe Pirrò
ABSTRACT. Community deception tackles the following problem: given a target community C inside a network G and a budget of updates β (e.g., edge removal and additions), what is the best way (i.e., optimization of some function φG(C)) to perform such updates in a way that C can escape to a detector D (i.e., a community detection algorithm)? This paper aims at: (i) presenting an analysis of the state-of-the-art deception techniques; (ii) evaluating state-of-the-art deception techniques: (iii) making available a library of techniques to practitioners and researchers.
Qi Yang, Khizar Qureshi and Tauhid Zaman
Mitigating the Backfire Effect Using Pacing and Leading
PRESENTER: Qi Yang
ABSTRACT. Online social networks create echo-chambers where people are infrequently exposed to opposing opinions. Even if such exposure oc- curs, the persuasive effect may be minimal or nonexistent. Recent stud- ies have shown that exposure to opposing opinions causes a backfire effect, where people become more steadfast in their original beliefs. We conducted a longitudinal field experiment on Twitter to test methods that mitigate the backfire effect while exposing people to opposing opin- ions. Our subjects were Twitter users with anti-immigration sentiment. The backfire effect was defined as an increase in the usage frequency of extreme anti-immigration language in the subjects' posts. We used au- tomated Twitter accounts, or bots, to apply different treatments to the subjects. One bot posted only pro-immigration content, which we refer to as arguing. Another bot initially posted anti-immigration content, then gradually posted more pro-immigration content, which we refer to as pacing and leading. We also applied a contact treatment in conjunction with the messaging based methods, where the bots liked the subjects' posts. We found that the most effective treatment was a combination of pacing and leading with contact. The least effective treatment was arguing with contact. In fact, arguing with contact consistently showed a backfire effect relative to a control group. These findings have many limitations, but they still have important implications for the study of political polarization, the backfire effect, and persuasion in online social networks.
17:00-18:15 Session Oral O9C: Ecological Networks and Food Webs
Jaime Iranzo
Somaye Sheykhali, Juan Fernandez-Gracia, Xabier Irigoien, Carlos M Duarte and Victor M Eguiluz
Dynamical models from microbial communities abundance data
PRESENTER: Juan Fernandez-Gracia
ABSTRACT. Microorganisms like bacteria, archaea and eukaryotes coexist in large and complex ecosystems. Actually, microbial communities form the largest and more diverse ecosystems on the planet. The interactions among their individuals are diverse, encompasing mutualism, comensalism, or competition. Measuring these interactions in direction and strength at a large scale is a challenging process that requires a combination of data analysis and modeling. Furthermore, the dynamic nature of the abundances of different species of microorganisms cannot be ignored to present a sound theory on microbial interactions. Here we use experimental data that reported the OTU (operational taxonomic units, quasi-equivalent to a species definition) abundance every day for a period of 20 days. These data on OTU abundances is fitted to a growth model that contains a local term that consists of a growth constant and an interaction term that encodes the effect of other OTU abundances on the self abundance of one OTU. The fitted model reveals thus the intrinsic growth rates of singles OTUs and the interaction network among OTUs. This interaction network contains both positive and negative ties, reflecting the synergetic or antagonistic nature of the interactions among OTUs. We performed statistical significance analysis to detect relevant interactions. Furthermore we apply several network tools to assess different properties of the network. For example, we cluster OTUs based on community detection algorithms to detect relevant groups. We also use a variety of centrality measures to disentangle which OTUs play a more important role in the network. Our approach offers a comprehensive view on microbial communities organizations from a dynamical perspective fusing modelling strategies and data analysis.
Cecilia Andreazzi, Mariana Vidal and Leandro Tambosi
Forest loss affects the structure of host-parasite networks in the Brazilian Atlantic forest
PRESENTER: Cecilia Andreazzi
ABSTRACT. Introduction Zoonotic infectious diseases are caused by parasites and pathogens that are shared by both humans and wild and domestic vertebrates [2]. They represent a large portion of the Neglected Tropical Diseases, which are chronic and debilitating infections prevalent in low-income countries [4].They are also the causative agent of many Emerging Infectious Diseases, including SARS, COVID-19 and MERS-Cov [3]. Environmental changes, mainly deforestation, forest fragmentation and conversion of natural habitats to agricultural use have the potential to impact the transmission cycle and epidemiological dynamics of zoonotic pathogens, which is related to pathogen spillover and disease emergence [2]. Because most zoonotic pathogens are harbored by multiple host species that share the pathogen, their emergence in a new host species, including humans, is just a special case of cross-species transmission. Deforestation for example, decreases the habitat available for many different species, leading to extinctions, host community simplification and increased abundance of generalist and opportunistic species, which are especially prone to transmit zoonotic pathogens [5]. Understanding how changes in host species composition affect parasite-host interaction networks and if the reconfiguration of interactions amplifies or dilutes the risk of disease emergence is a current challenge.We investigate how small mammal communities and their potential interactions with parasites are assembled according to landscape structure across the Brazilian Atlantic Forest.
Results We compute the ratio of forest cover and the total edge length between native forest and any other land-cover class for 210 different landscapes of Brazilian Atlantic Forest. The ranges of forest cover and edge length for the occurrence of each species are calculated based on the minimum and maximum percentage covers found in all the landscapes that they occurred and they are categorized as forest specialists and disturbance-adapted species (Fig. 1a). This allow us to define a sequence of host extinction events and the introduction of new species in communities according to increasing levels of forest loss. For each of the 69 small mammal species in those landscapes, we search the literature for their interactions with virus, bacteria, protozoa, fungi and helminth parasites. This results in a parasite-host metaweb with 300 parasites and 665 interactions, including 29 zoonotic pathogens (Fig. 1b). The local interaction networks are simulated based on the host-parasite metaweb, which allow us to evaluate how forest loss leads to changes in the organization of potential host-parasite networks. Eleven different scenarios of decreasing forest cover are simulated starting from an entirely forested landscape until a completely deforested environment The structure of the network assembled in each scenario are categorized in terms of its (i) connectance (i. e. the percentage of realized interactions), (ii) nestedness, which is a pattern characterized by a core of densely interacting generalist species that also interact with peripherical specialist species [6], and (iii) modularity, which is the extent to which species cluster into community groups oe modules [7]. Deforested landscapes are linked to high values of network connectance and nestedness, while modularity does not show such evident correlation with forest cover (Fig. 2a-c). Additionally, we found a maximum of small mammal species richness when the landscape reaches 60% of forest cover, and a maximum of potential parasites when forest cover is reduced to 20% of the landscape (Fig. 2d-e). The functional role played by each species is also affected by deforestation, since disturbance-adapted species have increased closeness and betweeness centralities in degraded landscapes. Our results show that landscapes with relatively low forest cover harbor a small number of mammal species but with higher potential to host many pathogens, indicating an important zoonotic potential in these communities. As a next step, we are developing probabilistic models based on biologically realistic rules for interaction rewiring. They will allow us to predict parasite spillover in degraded landscapes.
References 1. Gottdenker, N. L., Streicker, D. G., Faust, C. L., Carroll, C. R. Anthropogenic Land Use Change and Infectious Diseases: A Review of the Evidence. EcoHealth 11, 619632 (2014). 2. Keesing, F., Ostfeld, R. Impacts of biodiversity and biodiversity loss on zoonotic diseases. Proceedings of the National Academy of Sciences 118.17 (2021). 3. McCloskey, B., Dar, O., Zumla, A., Heymann, D. L. Emerging infectious diseases and pandemic potential: status quo and reducing risk of global spread. The Lancet infectious diseases 14(10): 1001-1010 (2014). 4. Hotez, P. J., Aksoy, S., Brindley, P. J., Kamhawi, S. What constitutes a neglected tropical disease? PLoS neglected tropical diseases, 14(1), e0008001 (2020). 5. Gibb, R., Redding, D.W., Chin, K.Q., Donnelly, C.A., Blackburn, T.M., Newbold, T., Jones, K. E. Zoonotic host diversity increases in human-dominated ecosystems. Nature 584, 398402 (2020). 6. AlmeidaNeto, M., Guimaraes, P., Guimaraes Jr, P. R., Loyola, R. D., Werner, U. A consistent metric for nestedness analysis in ecological systems: reconciling concept and measurement Oikos 117(8): 1227-1239 (2008). 7. Barber, M. J. Modularity and community detection in bipartite networks. Physical Review E 76(6): 066102 (2007).
Virginia Domínguez-García and Sonia Kéfi
The structure and robustness of tripartite ecological networks
PRESENTER: Virginia Domínguez-García
ABSTRACT. Until recently, most ecological network analyses have focused on a single interaction type. In nature, however, diverse interactions co-occur, each of them forming a layer of a `multilayer' network. Data including information on multiple interactions has recently started to emerge, giving us the opportunity to have a first glance at possible commonalities in the structure of these networks. We studied the structural features of 44 tripartite ecological networks from the literature, each composed of two layers of interactions (e.g. herbivory, parasitism, pollination), and investigated their fragility to species losses. We found that the way in which the different layers of interactions are connected to each other affect how perturbations spread in ecological communities. Our results highlight the importance of considering multiple interactions simultaneously to better gauge the robustness of ecological communities to species loss and to more reliably identify the species that are important for robustness.
Aniello Lampo, María J. Palazzi, Javier Borge-Holthoefer and Albert Solé-Ribalta
Hybrid structural arrangements mediate stability and feasibility in mutualistic networks
PRESENTER: Aniello Lampo
ABSTRACT. One of the largest debate in theoretical ecology concerns the emergence of structural patterns in interaction networks of biota. In addition to methodological problems, such as pattern identification, an important challenge regards the relationship between candidate architectures and the resulting dynamical behavior. In the case of mutualistic communities, the issue revolves mostly around two structural arrangements, nestedness and modularity, and two necessary requirements for ecological persistence: feasibility and stability. The former, defined as the probability to avoid extinctions, is strongly related to nestedness, while the latter is enhanced by modularity. Community persistence would require the two properties, and thus the coexistence of both nestedness and modularity, but this is problematic because of their antagonistic relationship. In this context, our work addresses the role of the interaction architecture in the maintenance of stability and feasibility, introducing the idea of hybrid architectural configurations. Specifically, we examine in-block nested networks, compound by weakly interlinked blocks (modules) with internal nested organization, and prove that they grant a balanced trade-off between stability and feasibility. Remarkably, we analyze a large amount of empirical communities and find that a relevant fraction of them exhibits a significant in-block nested character. We elaborate on the implications of these results, arguing that they provide new insights about the key properties ruling community assembly.
Giulio Tirabassi
Ecological Properties of Association Networks of Marine Microbes Abundances
ABSTRACT. Despite bacteria and viruses infecting them are a key part of the ocean ecosystem, we still have an incomplete understanding of their interaction. Given large the diversity of these subgroups, infection networks cannot be obtained simply by laboratory experiments. In recent years, association networks of microbial abundances have been used to study the ecological structure of this system. We show here that these association networks show significant ecological properties typical of host-parasite interactions, making them a good candidate for the underlying interaction network.
18:15-18:30 Session Closing Conference: Rosa M. Benito - Hocine Cherifi - Esteban Moro
Disclaimer | Powered by EasyChair Smart Program