Alexander Grimm, Claudio Tessone, Detecting nestedness in graphs, In: Complex Networks & Their Applications V : Proceedings of the 5th International Workshop on Complex Networks and their Applications, Springer, Zug, Switzerland, p. 171 - 182, 2017. (Book Chapter)
Many real-world networks have a nested structure. Examples range from biological ecosystems (e.g. mutualistic networks), industry systems (e.g. New York garment industry) to inter-bank networks (e.g. Fedwire bank network). A nested network has a graph topology such that a vertex’s neighborhood contains the neighborhood of vertices of lower degree. Thus, the adjacency matrix is stepwise, which can be found in both bipartite and non-bipartite networks. Despite the strict mathe- matical characterization and their common occurrence, it is not easy to detect nested graphs unequivocally. Among others, there exist three methods for detection and quantification of nestedness that are being widely used: BINMATNEST, NODF, and FCM. However, those methods fail in detecting nestedness for graphs with low (NODF) and high (NODF, BINMATNEST) density or were developed for bipartite networks (FCM). The common shortcoming of these approaches is the underlying asumption that all vertices belong to the nested component. However, many real- world networks have solely a sub-component (i.e. not all elements of the graph) that is nested. Thus, unveiling which vertices pertain to the nested component, is an important research question, unaddressed by the methods available so far. In this contribution, we study in detail the algorithm Nestedness detection based on Local Neighborhood (NESTLON). This algorithm detects nestedness on a broad range of nested graphs independently of their density and resorts solely on local information. By means of a benchmarking model we are able to tune the degree of nestedness in a controlled manner. Our results show that NESTLON outperforms both BIN- MATNEST and NODF. |
|
Alexander Grimm, Claudio Tessone, Detecting Nestedness in Graphs, In: Complexnetworks.org. 2016. (Conference Presentation)
|
|
Lukas Schönenberger, Radu Petru Tanase, Andrea Schenker-Wicki, Controlling complex policy problems: a multi-methodological approach using system dynamics and network controllability, In: Conference on Complex Systems. 2016. (Conference Presentation)
System dynamics (SD), an approach to modeling and simulating complex systems, has repeatedly demonstrated its value in contributing to the understanding and solution of complex policy problems. Typical areas of system dynamics application include modeling of policy problems related to public health, energy and the environment, social welfare, sustainable development, and security. One of the main challenges in system dynamics is that, due to a high degree of interdependent model variables and nonlinear relationships, the detection of model levers, i.e. variables capable of effectively and efficiently controlling complex policy problems, is exceedingly demanding. So, notwithstanding the usefulness of system dynamics in the analysis of these problems, the solution identification process is far from straightforward and in most cases trial-and-error driven. To address this challenge, we propose to combine system dynamics with network controllability to facilitate the detection of model levers. In essence, a system dynamics model can be thought of a web of interrelated causal factors that are assumed giving rise to the complex policy problem under study. Due to its web similarity, the structure of a system dynamics model can be accurately described as a directed weighted network, making it accessible to algorithmic exploration using concepts from the fields of graph theory and network science. Referring to recent research on control principles of complex networks, model levers are found first by calculating the size of the minimum driver set of the system dynamics model (network), second by computing all existing minimum driver sets, and third by ranking minimum driver set variables according to their control centrality. Variables with a high control centrality should be of primary interest to policy-makers when designing new solutions to complex policy problems. We demonstrate the proposed multimethodological approach on the basis of the World Dynamics model, a classic example from the system dynamics literature. |
|
Alexander Grimm, Nestedness in communication networks: From information exchange to topology, In: CCS 2016 in Amsterdam (Conference on Complex Systems 2016). 2016. (Conference Presentation)
|
|
Alexander Grimm, Nestedness in communication networks: From information exchange to topology, In: CCS 2016 in Amsterdam (Conference on Complex Systems 2016). 2016. (Conference Presentation)
|
|
Zhao Yang, René Algesheimer, Claudio Tessone, A Comparative Analysis of Community Detection Algorithms on Artificial Networks, Scientific Reports, Vol. 6, 2016. (Journal Article)
Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time. |
|
Radu Petru Tanase, Claudio Tessone, René Algesheimer, Identifying influential individuals from time-varying social interactions, In: Network Science. 2016. (Conference Presentation)
In the last years an increasing attention has been devoted to the identification of influential individuals and their use as super-spreaders of products or ideas. Most often, from the observed data researchers construct an influence network and identify the influencers as the most central individuals in this network or as the key players in the development of a dynamical process. However, in most practical situations there are at least two potential issues with this approach. First, the construction of the influence network is non-trivial as most often the influence relationships between people are not directly observable but rather aspects of their behavior. Second, even if the influence relationships were observable, the static network representation cannot capture their time-dynamical aspect.
We present a new approach to identify influential individuals from time varying social interactions which does not require constructing the influence network nor modeling social influence as a dynamical process. We consider that individuals become influential due to unobserved features they posses, which we call the latent potential to influence. This potential is revealed during social interactions and acknowledged by other participants through rewards (e.g. upvotes on discussion platforms). We uncover the latent potential to influence from the observed rewards using the influence potential (IP), a novel index we introduce here. To illustrate our approach we analyze two real-world systems: a news discussion forum (CNN) and a business review platform (Yelp). In both datasets we find few influencers, which is in agreement with the existing theory. We compare the results against a null model and show that the presence of such individuals is very unlikely to have occurred by chance. We validate the approach by dividing the datasets into a training and a test set and showing that the users with the highest IP in the training set are also the most influential in the test set. |
|
Zhao Yang, René Algesheimer, Claudio Tessone, A Comparative Analysis of Community Detection Algorithms on Artificial Networks, In: Network Science. 2016. (Conference Presentation)
|
|
Claudio Tessone, Designing wise crowds: Social influence and competition, In: Collective behavior in the big data area: can we enhance collective intelligence in human groups?. 2016. (Conference Presentation)
|
|
Radu Petru Tanase, Claudio Tessone, René Algesheimer, The influence potential. A new approach to identify influential individuals from time-varying social interactions, In: Netsci-X. 2016. (Conference Presentation)
Understanding how people influence or are influenced by their peers can help us understand the flow of market trends, product adoption and diffusion processes. In the last years an increas- ing attention has been devoted to identifying the most influential individuals and using them as super-spreaders of products or ideas. Most often, from the observed data researchers construct an influence network and identify the influentials as the most central individuals in this network or as the key players in the development of a dynamical process. However, in most practical situations there are at least two potential issues with this approach. First, the construction of the influence network is non-trivial as most often the influence relationships between people are not directly observable but rather aspects of people’s behavior. Furthermore, even if the influence relationships were observable, the static network representation cannot capture their time-dynamical aspect. Second, identifying influential individuals based on their role in a dynamical process is sensitive to the model chosen and to the assumed role influentials should play in the process. In this article we present a model-free approach to identify influential individuals from time varying social in- teractions which does not require constructing the influence network nor modeling social influence as a dynamical process. We start by introducing the influence potential (IP), a novel index that captures the intrinsic ability of individuals to consistently influence others while controlling for the total number of individuals in the process. We validate our results by computing an adapted version of the area under the curve (AUC) as indicator of the in-sample prediction accuracy and further use this to identify how many influential individuals are in a dataset. To illustrate our approach we analyze two real world systems: a news discussion forum extracted from cnn.com and a business review platform extracted from yelp.com. In both datasets we identify a low number of users with high influence potential relative to the entire user base. This implies that if we are interested to steer the user behavior on the platform, we can design intervention campaigns tar- geting influential individuals but with very few reliable targets. Furthermore, we compare the two datasets and find that Yelp has a higher percentage of individuals with high influence potential. This suggests that in the Yelp dataset it is relatively easier to locate potential targets, which might have important implications for comparing the intervention costs on the two platforms. |
|
Mario V Tomasello, Claudio Tessone, Frank Schweitzer, A model of dynamic rewiring and knowledge exchange in R&D networks, Advances in Complex Systems, Vol. 19 (1), 2016. (Journal Article)
This paper investigates the process of knowledge exchange in inter-firm Research and Development (R&D) alliances by means of an agent-based model. Extant research has pointed out that firms select alliance partners considering both network-related and network-unrelated features (e.g., social capital versus complementary knowledge stocks). In our agent-based model, firms are located in a metric knowledge space. The interaction rules incorporate an exploration phase and a knowledge transfer phase, during which firms search for a new partner and then evaluate whether they can establish an alliance to exchange their knowledge stocks. The model parameters determining the overall system properties are the rate at which alliances form and dissolve and the agents' interaction radius. Next, we define a novel indicator of performance, based on the distance traveled by the firms in the knowledge space. Remarkably, we find that - depending on the alliance formation rate and the interaction radius - firms tend to cluster around one or more attractors in the knowledge space, whose position is an emergent property of the system. And, more importantly, we find that there exists an inverted U-shaped dependence of the network performance on both model parameters. |
|
Juan Ignacio Perotti, Claudio Tessone, Guido Caldarelli, Hierarchical mutual information for the comparison of hierarchical community structures in complex networks, Physical review. E, Statistical, nonlinear, and soft matter physics, Vol. 92, 2015. (Journal Article)
The quest for a quantitative characterization of community and modular structure of complex networks produced a variety of methods and algorithms to classify different networks. However, it is not clear if such methods provide consistent, robust, and meaningful results when considering hierarchies as a whole. Part of the problem is the lack of a similarity measure for the comparison of hierarchical community structures. In this work we give a contribution by introducing the hierarchical mutual information, which is a generalization of the traditional mutual information and makes it possible to compare hierarchical partitions and hierarchical community structures. The normalized version of the hierarchical mutual information should behave analogously to the traditional normalized mutual information. Here the correct behavior of the hierarchical mutual information is corroborated on an extensive battery of numerical experiments. The experiments are performed on artificial hierarchies and on the hierarchical community structure of artificial and empirical networks. Furthermore, the experiments illustrate some of the practical applications of the hierarchical mutual information, namely the comparison of different community detection methods and the study of the consistency, robustness, and temporal evolution of the hierarchical modular structure of networks. |
|
Claudio Tessone, David Garcia, Nicolas Perony, Pavlin Mavrodiev, From social media to endogenous activity: Their effects on Bitcoin price bubbles and user adoption, In: Computational and Methodological Statistics. 2015. (Conference Presentation)
What is the role of social interactions in the creation of price bubbles? Answering this question requires obtaining collective behavioural traces generated by the activity of a large number of actors. Digital currencies offer a unique possibility to measure socio-economic signals from such digital traces. We focus on Bitcoin, the most popular cryptocurrency. Bitcoin has experienced periods of rapid increase in exchange rates (price) followed by sharp decline; we hypothesise that these fluctuations are largely driven by the interplay between different social phenomena. We thus quantify four socio-economic signals about Bitcoin from large datasets: price on online exchanges, volume of word-of-mouth communication in online social media, volume of information search and user base growth. By using vector autoregression, we identify two positive feedback loops that lead to price bubbles in the absence of exogenous stimuli: one driven by word of mouth, and the other by new Bitcoin adopters. We also observe that spikes in information search, presumably linked to external events, precede drastic price declines. We further identify users within the Bitcoin transaction network, and show how the user adoption and endogenous economic activity (signalled by both: the economic transactions between them, and capital accumulation) makes this system a rather different one with respect to how it was originally envisioned. |
|
Radu Petru Tanase, Claudio Tessone, René Algesheimer, Who do we follow? A new approach to identify influential individuals from time-varying social interactions., In: CCS 2015. 2015. (Conference Presentation)
|
|
René Algesheimer, Claudio Tessone, Who do we follow? A new approach to identify influential individuals from time-varying social interactions., In: CCS 2015. 2015. (Conference Presentation)
|
|
Mario Tomasello, The effect of R&D collaborations on firms' technological positions, In: 10th International Forum on Knowledge Asset Dynamics, Bari, 2015-06-10. (Conference or Workshop Paper published in Proceedings)
Purpose - We develop an agent- based model to reproduce the processes of link formation and knowledge exchange in a Research and Development (R&D) inter-organizational network.
Methodology - In our model, agents form links based on their network features, i.e. their belonging to one of the network's circles of influence and their previous alliance history, and then exchange knowledge with their partners, thus modifying their positions in a metric knowledge space. Furthermore, we validate the model against real data using a two-step approach. Through the Thomson Reuters SDC alliance dataset, we estimate the model parameters related to the link formation, thus reproducing the topology of the resulting R&D network. Subsequently, using the NBER data on firm patents, we estimate the parameters related to the knowledge exchange process, thus evaluating the rate at which firms exchange knowledge and the duration of the R&D alliances themselves.
Originality - The underlying knowledge space that we consider in our real example is defined by IPC patent classes, allowing for a precise quantification of every firm's knowledge position. Our novel data-driven approach allows us to unveil the complex interdependencies between the firms' network embeddedness and their technological positions. Through the validation of our model, we find that real R&D alliances have a duration of around two years, and that the subsequent knowledge exchange occurs at a very low rate. Most of the alliances, indeed, have no consequence on the partners' knowledge positions: this suggests that a firm's position - evaluated through its patents is rather a determinant than a consequence of its R&D alliances. Finally, we propose an indicator of collaboration performance for the whole network. We find that the real R&D network does not maximize such an indicator.
Practical implications - Our study shows that there exist configurations that can be both realistic and optimized with respect to the collaboration performance. Effective policies to obtain an optimized collaboration network - as suggested by our model - would incentivize shorter R&D alliances and higher knowledge exchange rates, for instance including rewards for quick co-patenting by allied firms. |
|
Claudio Tessone, Network volatility as a source of collective dynamics, In: International Conference on Computational Social Science. 2015. (Conference Presentation)
Many systems exhibit patterns of interaction that are largely sparse and volatile at the same time. Sparsity is a common trait in networks where links are costly, or the nodes involved have some kind of capacity constraints; examples of this kind of behaviour are scientific and R&D collaborations and processes of opinion formation and disease spreading. In all these examples, agents do not maintain active the links to all their partners continuously. The sparsity of the network at any point in time determines the existence of a stable backbone whose evolution is slower than the typical time-scales of link creation and removal. The network backbone implies that between two consecutive observational time-windows, a footprint of the aggregated network will persist. However, in general in temporal networks, not all edges persist, and therefore there exists also a characteristic time after which a given instantaneous network becomes largely decorrelated with the previous one. Volatility then refers to the renewal process of edges in the stable backbone; the more fluid is said process, the more volatile the temporal network.
When a dynamical process unravels on a temporal network, three ingredients have competing effects on the global properties of the system. First, the characteristic time-scales of the dynamical process itself; this has also influence on the convergence times for global phenomena to emerge. Second, the lifetime distribution of edges in the network, that determines the extent to which dynamical states can propagate. Third, the typical backbone of the network; a simple proxy for this quantity is the typical network density that is observed, instantaneously, in the system.
In this Contribution, we study the role of network volatility in paradigmatic models of spreading developing on temporal networks, namely the Susceptible-Infected-Susceptible and Susceptible-Infected- Recovered-Susceptible ones. To do so, we introduce a minimalistic model of temporal networks such that different aspects of network volatility can be studied. In particular, we investigate under which conditions the relative sparseness and edge volatility of the temporal network can replace global connectivity in triggering collective behaviour. We show that collective phenomena can emerge purely induced by network dynamics when the network volatility is sufficiently large. We further demonstrate that long-range cor- relations can emerge in the system, even if the system remains largely disconnected while the temporal network evolves.
Interestingly, we demonstrate a non-trivial relationship between the different aspects of network volatility, like the relative size of the stable backbone ρ, and the emergent properties of the processes taking place at the nodes of the system. First, it is clear that there exists a critical point for the size of the stable backbone such that the instantaneous network becomes disconnected (i.e. it experiences a percolation transition). Then, we show that also as a function of the size of the stable backbone, the dynamical processes analysed experience phase transitions towards different dynamical states (like coexistence, or synchronous behaviour) purely induced by the network dynamics. We show that such dynamic phase transition is not related to the percolation transition mentioned above, having both different critical points. Therefore, the phenomenon we show is not a simple results of the instantaneous network becoming dis- connected, but indeed an emergent property of network dynamics.
|
|