BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Marco Tomassini

Marco Tomassini contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
physics.soc-phArtificial IntelligenceSocial and Information NetworksNeural and Evolutionary Computingcond-mat.stat-mechcond-mat.dis-nnnlin.AOPopulations and Evolution

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2022arXiv

Complex Networks Analysis of the Energy Landscape of the Low Autocorrelation Binary Sequences Problem

We provide an up-to-date view of the structure of the energy landscape of the low autocorrelation binary sequences problem, a typical representative of the $NP$-hard class. To study the landscape features of interest we use the local optima network methodology through exhaustive extraction of the optima graphs for problem sizes up to $24$. Several metrics are used to characterize the networks: number and type of optima, optima basins structure, degree and strength distributions, shortests paths to the global optima, and random walk-based centrality of optima. Taken together, these metrics provide a quantitative and coherent explanation for the difficulty of the low autocorrelation binary sequences problem and provide information that could be exploited by optimization heuristics for this problem, as well as for a number of other problems having a similar configuration space structure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generating Robust and Efficient Networks Under Targeted Attacks

Much of our commerce and traveling depend on the efficient operation of large scale networks. Some of those, such as electric power grids, transportation systems, communication networks, and others, must maintain their efficiency even after several failures, or malicious attacks. We outline a procedure that modifies any given network to enhance its robustness, defined as the size of its largest connected component after a succession of attacks, whilst keeping a high efficiency, described in terms of the shortest paths among nodes. We also show that this generated set of networks is very similar to networks optimized for robustness in several aspects such as high assortativity and the presence of an onion-like structure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Binary birth-death dynamics and the expansion of cooperation by means of self-organized growth

Natural selection favors the more successful individuals. This is the elementary premise that pervades common models of evolution. Under extreme conditions, however, the process may no longer be probabilistic. Those that meet certain conditions survive and may reproduce while others perish. By introducing the corresponding binary birth-death dynamics to spatial evolutionary games, we observe solutions that are fundamentally different from those reported previously based on imitation dynamics. Social dilemmas transform to collective enterprises, where the availability of free expansion ranges and limited exploitation possibilities dictates self-organized growth. Strategies that dominate are those that are collectively most apt in meeting the survival threshold, rather than those who succeed in exploiting others for unfair benefits. Revisiting Darwinian principles with the focus on survival rather than imitation thus reveals the most counterintuitive ways of reconciling cooperation with competition.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Local Optima Networks: A New Model of Combinatorial Fitness Landscapes

This chapter overviews a recently introduced network-based model of combinatorial landscapes: Local Optima Networks (LON). The model compresses the information given by the whole search space into a smaller mathematical object that is a graph having as vertices the local optima and as edges the possible weighted transitions between them. Two definitions of edges have been proposed: basin-transition and escape-edges, which capture relevant topological features of the underlying search spaces. This network model brings a new set of metrics to characterize the structure of combinatorial landscapes, those associated with the science of complex networks. These metrics are described, and results are presented of local optima network extraction and analysis for two selected combinatorial landscapes: NK landscapes and the quadratic assignment problem. Network features are found to correlate with and even predict the performance of heuristic search algorithms operating on these problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Evolution of Cooperation on Spatially Embedded Networks

In this work we study the behavior of classical two-person, two-strategies evolutionary games on networks embedded in a Euclidean two-dimensional space with different kinds of degree distributions and topologies going from regular to random, and to scale-free ones. Using several imitative microscopic dynamics, we study the evolution of global cooperation on the above network classes and find that specific topologies having a hierarchical structure and an inhomogeneous degree distribution, such as Apollonian and grid-based networks, are very conducive to cooperation. Spatial scale-free networks are still good for cooperation but to a lesser degree. Both classes of networks enhance average cooperation in all games with respect to standard random geometric graphs and regular grids by shifting the boundaries between cooperative and defective regions. These findings might be useful in the design of interaction structures that maintain cooperation when the agents are constrained to live in physical two-dimensional space.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Clustering of Local Optima in Combinatorial Fitness Landscapes

Using the recently proposed model of combinatorial landscapes: local optima networks, we study the distribution of local optima in two classes of instances of the quadratic assignment problem. Our results indicate that the two problem instance classes give rise to very different configuration spaces. For the so-called real-like class, the optima networks possess a clear modular structure, while the networks belonging to the class of random uniform instances are less well partitionable into clusters. We briefly discuss the consequences of the findings for heuristically searching the corresponding problem spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Communities of Minima in Local Optima Networks of Combinatorial Spaces

In this work we present a new methodology to study the structure of the configuration spaces of hard combinatorial problems. It consists in building the network that has as nodes the locally optimal configurations and as edges the weighted oriented transitions between their basins of attraction. We apply the approach to the detection of communities in the optima networks produced by two different classes of instances of a hard combinatorial optimization problem: the quadratic assignment problem (QAP). We provide evidence indicating that the two problem instance classes give rise to very different configuration spaces. For the so-called real-like class, the networks possess a clear modular structure, while the optima networks belonging to the class of random uniform instances are less well partitionable into clusters. This is convincingly supported by using several statistical tests. Finally, we shortly discuss the consequences of the findings for heuristically searching the corresponding problem spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Complex-network analysis of combinatorial spaces: The NK landscape case

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces. We use the well-known family of NK landscapes as an example. In our case the inherent network is the graph whose vertices represent the local maxima in the landscape, and the edges account for the transition probabilities between their corresponding basins of attraction. We exhaustively extracted such networks on representative NK landscape instances, and performed a statistical characterization of their properties. We found that most of these network properties are related to the search difficulty on the underlying NK landscapes with varying values of K.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Cooperation on Social Networks and Its Robustness

In this work we have used computer models of social-like networks to show by extensive numerical simulations that cooperation in evolutionary games can emerge and be stable on this class of networks. The amounts of cooperation reached are at least as much as in scale-free networks but here the population model is more realistic. Cooperation is robust with respect to different strategy update rules, population dynamics, and payoff computation. Only when straight average payoff is used or there is high strategy or network noise does cooperation decrease in all games and disappear in the Prisoner's Dilemma.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes

This paper extends a recently proposed model for combinatorial landscapes: Local Optima Networks (LON), to incorporate a first-improvement (greedy-ascent) hill-climbing algorithm, instead of a best-improvement (steepest-ascent) one, for the definition and extraction of the basins of attraction of the landscape optima. A statistical analysis comparing best and first improvement network models for a set of NK landscapes, is presented and discussed. Our results suggest structural differences between the two models with respect to both the network connectivity, and the nature of the basins of attraction. The impact of these differences in the behavior of search heuristics based on first and best improvement local search is thoroughly discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local optima networks and the performance of iterated local search

Local Optima Networks (LONs) have been recently proposed as an alternative model of combinatorial fitness landscapes. The model compresses the information given by the whole search space into a smaller mathematical object that is the graph having as vertices the local optima and as edges the possible weighted transitions between them. A new set of metrics can be derived from this model that capture the distribution and connectivity of the local optima in the underlying configuration space. This paper departs from the descriptive analysis of local optima networks, and actively studies the correlation between network features and the performance of a local search heuristic. The NK family of landscapes and the Iterated Local Search metaheuristic are considered. With a statistically-sound approach based on multiple linear regression, it is shown that some LONs' features strongly influence and can even partly predict the performance of a heuristic search algorithm. This study validates the expressive power of LONs as a model of combinatorial fitness landscapes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance

Recent developments in fitness landscape analysis include the study of Local Optima Networks (LON) and applications of the Elementary Landscapes theory. This paper represents a first step at combining these two tools to explore their ability to forecast the performance of search algorithms. We base our analysis on the Quadratic Assignment Problem (QAP) and conduct a large statistical study over 600 generated instances of different types. Our results reveal interesting links between the network measures, the autocorrelation measures and the performance of heuristic search algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Supercooperation in Evolutionary Games on Correlated Weighted Networks

In this work we study the behavior of classical two-person, two-strategies evolutionary games on a class of weighted networks derived from Barabási-Albert and random scale-free unweighted graphs. Using customary imitative dynamics, our numerical simulation results show that the presence of link weights that are correlated in a particular manner with the degree of the link endpoints, leads to unprecedented levels of cooperation in the whole games' phase space, well above those found for the corresponding unweighted complex networks. We provide intuitive explanations for this favorable behavior by transforming the weighted networks into unweighted ones with particular topological properties. The resulting structures help to understand why cooperation can thrive and also give ideas as to how such supercooperative networks might be built.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Local Optima Networks of NK Landscapes with Neutrality

In previous work we have introduced a network-based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. By using two known neutral variants of the NK family (i.e. NKp and NKq) in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Local Optima Networks of the Quadratic Assignment Problem

Using a recently proposed model for combinatorial landscapes, Local Optima Networks (LON), we conduct a thorough analysis of two types of instances of the Quadratic Assignment Problem (QAP). This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of 'inherent network' of potential energy surfaces proposed in physical-chemistry. The local optima networks extracted from the so called uniform and real-like QAP instances, show features clearly distinguishing these two types of instances. Apart from a clear confirmation that the search difficulty increases with the problem dimension, the analysis provides new confirming evidence explaining why the real-like instances are easier to solve exactly using heuristic search, while the uniform instances are easier to solve approximately. Although the local optima network model is still under development, we argue that it provides a novel view of combinatorial landscapes, opening up the possibilities for new analytical tools and understanding of problem difficulty in combinatorial optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

NK landscapes difficulty and Negative Slope Coefficient: How Sampling Influences the Results

Negative Slope Coefficient is an indicator of problem hardness that has been introduced in 2004 and that has returned promising results on a large set of problems. It is based on the concept of fitness cloud and works by partitioning the cloud into a number of bins representing as many different regions of the fitness landscape. The measure is calculated by joining the bins centroids by segments and summing all their negative slopes. In this paper, for the first time, we point out a potential problem of the Negative Slope Coefficient: we study its value for different instances of the well known NK-landscapes and we show how this indicator is dramatically influenced by the minimum number of points contained into a bin. Successively, we formally justify this behavior of the Negative Slope Coefficient and we discuss pros and cons of this measure.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Swiss Board Directors Network in 2009

We study the networks formed by the directors of the most important Swiss boards and the boards themselves for the year 2009. The networks are obtained by projection from the original bipartite graph. We highlight a number of important statistical features of those networks such as degree distribution, weight distribution, and several centrality measures as well as their interrelationships. While similar statistics were already known for other board systems, and are comparable here, we have extended the study with a careful investigation of director and board centrality, a k-core analysis, and a simulation of the speed of information propagation and its relationships with the topological aspects of the network such as clustering and link weight and betweenness. The overall picture that emerges is one in which the topological structure of the Swiss board and director networks has evolved in such a way that special actors and links between actors play a fundamental role in the flow of information among distant parts of the network. This is shown in particular by the centrality measures and by the simulation of a simple epidemic process on the directors network.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Evolution of Coordination in Social Networks: A Numerical Study

Coordination games are important to explain efficient and desirable social behavior. Here we study these games by extensive numerical simulation on networked social structures using an evolutionary approach. We show that local network effects may promote selection of efficient equilibria in both pure and general coordination games and may explain social polarization. These results are put into perspective with respect to known theoretical results. The main insight we obtain is that clustering, and especially community structure in social networks has a positive role in promoting socially efficient outcomes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Worldwide spreading of economic crisis

We model the spreading of a crisis by constructing a global economic network and applying the Susceptible-Infected-Recovered (SIR) epidemic model with a variable probability of infection. The probability of infection depends on the strength of economic relations between the pair of countries, and the strength of the target country. It is expected that a crisis which originates in a large country, such as the USA, has the potential to spread globally, like the recent crisis. Surprisingly we show that also countries with much lower GDP, such as Belgium, are able to initiate a global crisis. Using the {\it k}-shell decomposition method to quantify the spreading power (of a node), we obtain a measure of ``centrality'' as a spreader of each country in the economic network. We thus rank the different countries according to the shell they belong to, and find the 12 most central countries. These countries are the most likely to spread a crisis globally. Of these 12 only six are large economies, while the other six are medium/small ones, a result that could not have been otherwise anticipated. Furthermore, we use our model to predict the crisis spreading potential of countries belonging to different shells according to the crisis magnitude.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Conformity Hinders the Evolution of Cooperation on Scale-Free Networks

We study the effects of conformity, the tendency of humans to imitate locally common behaviors, in the evolution of cooperation when individuals occupy the vertices of a graph and engage in the one-shot Prisoner's Dilemma or the Snowdrift game with their neighbors. Two different graphs are studied: rings (one-dimensional lattices with cyclic boundary conditions) and scale-free networks of the Barabasi-Albert type. The proposed evolutionary-graph model is studied both by means of Monte Carlo simulations and an extended pair-approximation technique. We find improved levels of cooperation when evolution is carried on rings and individuals imitate according to both the traditional pay-off bias and a conformist bias. More important, we show that scale-free networks are no longer powerful amplifiers of cooperation when fair amounts of conformity are introduced in the imitation rules of the players. Such weakening of the cooperation-promoting abilities of scale-free networks is the result of a less biased flow of information in scale-free topologies, making hubs more susceptible of being influenced by less-connected neighbors.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Evolutionary Games on Networks and Payoff Invariance Under Replicator Dynamics

The commonly used accumulated payoff scheme is not invariant with respect to shifts of payoff values when applied locally in degree-inhomogeneous population structures. We propose a suitably modified payoff scheme and we show both formally and by numerical simulation, that it leaves the replicator dynamics invariant with respect to affine transformations of the game payoff matrix. We then show empirically that, using the modified payoff scheme, an interesting amount of cooperation can be reached in three paradigmatic non-cooperative two-person games in populations that are structured according to graphs that have a marked degree inhomogeneity, similar to actual graphs found in society. The three games are the Prisoner's Dilemma, the Hawks-Doves and the Stag-Hunt. This confirms previous important observations that, under certain conditions, cooperation may emerge in such network-structured populations, even though standard replicator dynamics for mixing populations prescribes equilibria in which cooperation is totally absent in the Prisoner's Dilemma, and it is less widespread in the other two games.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Mutual Trust and Cooperation in the Evolutionary Hawks-Doves Game

Using a new dynamical network model of society in which pairwise interactions are weighted according to mutual satisfaction, we show that cooperation is the norm in the Hawks-Doves game when individuals are allowed to break ties with undesirable neighbors and to make new acquaintances in their extended neighborhood. Moreover, cooperation is robust with respect to rather strong strategy perturbations. We also discuss the empirical structure of the emerging networks, and the reasons that allow cooperators to thrive in the population. Given the metaphorical importance of this game for social interaction, this is an encouraging positive result as standard theory for large mixing populations prescribes that a certain fraction of defectors must always exist at equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Evolution of Cooperation and Coordination in a Dynamically Networked Society

Situations of conflict giving rise to social dilemmas are widespread in society and game theory is one major way in which they can be investigated. Starting from the observation that individuals in society interact through networks of acquaintances, we model the co-evolution of the agents' strategies and of the social network itself using two prototypical games, the Prisoner's Dilemma and the Stag Hunt. Allowing agents to dismiss ties and establish new ones, we find that cooperation and coordination can be achieved through the self-organization of the social network, a result that is non-trivial, especially in the Prisoner's Dilemma case. The evolution and stability of cooperation implies the condensation of agents exploiting particular game strategies into strong and stable clusters which are more densely connected, even in the more difficult case of the Prisoner's Dilemma.

0 citations0 reviewsNo code linkedOpen access