Search

This paper explores the influence maximization problem for the weighted cascade model by considering an approach based on Shapley value and Extremal Optimization. The Shapley value is a solution concept in cooperative game theory that, given a total value of the game assigns to each player a value as part of it, computed as its marginal contribution to all possible coalitions of players. In the weighted cascade model we consider adding and updating nodes in the initial set during the extremal optimization search based on their Shapley value in an approach already tested for the independent cascade model. Comparisons with other methods by means of numerical experiments show that results reported by this approach are promising, prompting for further research in this direction.

The community detection problem is an emerging part of complex networks, identifying communities can offer important insights for the network. Several methods exist for detecting communities in single layered networks, however for multilayered the problem has not been so thoroughly studied. In this paper we propose a new method for the community detection problem for multilayered network, based on the idea of semi-aggregation of different layers. We compare the proposed method with existing approaches in the literature on benchmark problems and apply our method on a co-authorship multiplex network.

Representation and analysis of publication data in the form of a network has become a common method of illustrating and evaluating the scientific output of a group or of a scientific field. Co-authorship networks also reveal patterns and collaboration practices. In this paper we propose the use of a hypergraph model—a generalized network—to represent publication data by considering papers as hypergraph nodes. Hyperedges, connecting the nodes, represent the authors connecting all their papers. We show that this representation is more straightforward than other authorship network models. Using the hypergraph model we propose a collaboration measure of an author that reflects the influence of that author over the collaborations of its co-authors. We illustrate the introduced concepts by analyzing publishing data of computer scientists and mathematicians in Romania over a 10 year period.

Determining the critical nodes in a complex network is an essential computation problem. Several variants of this problem have emerged due to its wide applicability in network analysis. In this article we study the bi-objective critical node detection problem (BOCNDP), which is a new variant of the well-known critical node detection problem, optimizing two objectives at the same time: maximizing the number of connected components and minimizing the variance of their cardinalities. Evolutionary multi-objective algorithms (EMOA) are a straightforward choice to solve this type of problem. We propose three different smart initialization strategies which can be incorporated into any EMOA. These initialization strategies take into account the basic properties of the networks. They are based on the highest degree, random walk (RW) and depth-first search. Numerical experiments were conducted on synthetic and real-world network data. The three different initialization types significantly improve the performance of the EMOA.

The paper proposes a general game theoretical model, called capacity demand game, for treating simultaneous capacity requests in scarce-resource cognitive radio (CR) environments. The approach is that of non-cooperative games describing CR interactions in terms of radio resource access. Experiments reveal stable states (equilibria) that favour an equitable usage of radio resources to the benefit of all participants. Several equilibria are detected and discussed: Nash (NE), Pareto, joint Nash–Pareto, and Lorenz equilibrium.

The problem of Network Influence Maximization is approached by an Extremal Optimization algorithm called Shapley value Extremal Optimization (SvEO). The influence maximization problem for the independent cascade model is considered as a cooperative game. In this cooperative game players seek to choose seeder nodes to maximize the value of the game computed as the size of the influence set of their cascade model by maximizing their average marginal contribution to all possible player coalitions (i.e. subsets of the seeder set). SvEO is compared with other influence maximization algorithms by means of numerical experiments, with promising results. Possible implications of the use of the Shapley value are discussed using a network constructed from highly cited publication data in the field of computer science.

Influence Extremal Optimization (InfEO) is an algorithm based on Extremal Optimization, adapted for the influence maximization problem for the independent cascade model. InfEO maximizes the marginal contribution of a node to the influence set of the model. Numerical experiments are used to compare InfEO with other influence maximization methods, indicating the potential of this approach. Practical results are discussed on a network constructed from publication data in the field of computer science.

The map equation is one of the most efficient methods of evaluating a possible community structure of a network, computed by using Shanon’s entropy and probabilities that a random walker would exit a community or would wonder inside it. Infomap, the method that optimizes the map equation to reveal community structures, is one of the most efficient computational approach to this problem when dealing with weighted, directed or hierarchical networks. However, for some unweighted and undirected networks, Infomap fails completely to uncover any structure. In this paper we propose an alternate way of computing probabilities used by the map equation by adding information about 3-cliques corresponding to links in order to enhance the behavior of Infomap in unweighted networks. Numerical experiments performed on standard benchmarks show the potential of the approach.

The Generalized Berge-Zhukovskii equilibrium extends the Berge-Zhukovskii equilibrium problem by introducing constraints over the set of strategy profiles. The new equilibrium is computed in a dynamic environment by using an evolutionary dynamic equilibrium tracking algorithm. Numerical experiments for the generalized Cournot duopoly illustrate the capability of the approach.

Noisy extremal optimization is a new optimization-based heuristic designed to identify the community structure of complex networks by maximizing the modularity function. The extremal optimization algorithm evolves configurations that represent network covers, composed of nodes evaluated separately. Each iteration, a number of nodes having the worst fitness values are randomly assigned different communities. A network shifting procedure is used to induce a noise in the population as a diversity preserving mechanism. Numerical experiments, performed on synthetic and real-world networks, illustrate the potential of this approach.

Recent advances in brain imaging technology, coupled with large-scale brain research projects, such as the BRAIN initiative in the U.S. and the European Human Brain Project, allow us to capture brain activity in unprecedented details. In principle, the observed data is expected to substantially shape our knowledge about brain activity, which includes the development of new biomarkers of brain disorders. However, due to the high dimensionality, the analysis of the data is challenging, and selection of relevant features is one of the most important analytic tasks. In many cases, due to the complexity of search space, evolutionary algorithms are appropriate to solve the aforementioned task. In this chapter, we consider the feature selection task from the point of view of classification tasks related to functional magnetic resonance imaging (fMRI) data. Furthermore, we present an empirical comparison of conventional LASSO-based feature selection and a novel feature selection approach designed for fMRI data based on a simple genetic algorithm.

A Cournot oligopoly is used as a benchmark for Nash equilibria tracking and detection in a dynamic setting. Several dynamics that induce different trajectories for the equilibria are considered: random, linear, cosine, and spiral. A new Extremal Optimization based method is tested on the proposed dynamic setting.

Berge-Zhukovskii equilibrium is an alternate solution concept to Nash equilibrium that induces cooperation in non-cooperative games. A solution of a game is a Berge-Zhukovskii equilibrium if the payoff of each player cannot increase regardless of what the other players do. The Berge-Zhukovskii equilibrium has been found to be us useful in trust games. We propose a new method, based on evolutionary algorithms, to detect and track the Berge-Zhukovskii equilibrium of a game considering a discrete-time dynamic environment. To test our method we propose a new dynamic multiplayer game model, based on the Voluntary contribution mechanism. Numerical results show the potential of the proposed method.

Community structure detection algorithms are used to identify groups of nodes that are more connected to each other than to the rest of the network. Multipartite networks are a special type of network in which nodes are divided into partitions such that there are no links between nodes in the same partition. However, such nodes may belong to the same community, making the identification of the community structure of a multipartite network computationally challenging. In this paper, we propose a new fitness function that takes into account the information induced by existing links in the network by considering shadowed connections between nodes that have a common neighbor. The existence of a correct fitness function, i.e. one whose optimum values correspond to the community structure of the network, enables the design and use of optimization-based heuristics for solving this problem. We use numerical experiments performed on artificial benchmarks to illustrate the effectiveness of this function used within an extremal optimization based algorithm and compared to existing approaches. As a direct application, a multipartite network constructed from a direct marketing database is analyzed.

The network community structure detection problem consists in finding groups of nodes that are more connected to each other than to the rest of the network. While many methods have been designed to deal with this problem for general networks, there are few methods that deal with bipartite ones. In this paper we explore the behavior of an optimization method designed for identifying the community structure of unweighted networks when dealing with bipartite networks. We find that by using the specific Barber modularity, results are comparable with those reported in literature.

The development of search-based algorithms forautomatic test case generation is a key issue in the researcharea of software testing. Evolutionary algorithms have beenfrequently used for this purpose due to their ability to solvecomplex optimization problems. In this paper we introduce anovel approach to the automatic test-case generation problemfor reactive software systems. We build upon our previouswork where we defined a test generation framework based onparameterized executable environment models written in theLutin language. The main contribution of this paper is theapplication of a self-adaptive evolutionary algorithm, JADE inthe context of our test generation framework and the evaluationof its performance on a realistic reactive system written in Scade. Our preliminary results show that adaptive differential evolutioncan be used efficiently to increase the structural coverage of thesystem under test and is easier to use due to the fewer parametersthat require fine-tuning.

The network community detection problem consists in identifying groups of nodes that are more densely connected to each other than to the rest of the network. The lack of a formal definition for the notion of community led to the design of various solution concepts and computational approaches to this problem, among which those based on optimization and, more recently, on game theory, received a special attention from the heuristic community. The former ones define the community structure as an optimum value of a fitness function, while the latter as a game equilibrium. Both are appealing as they allowed the design and use of various heuristics. This paper analyses the behavior of such a heuristic that is based on extremal optimization, when used either as an optimizer or within a game theoretic setting. Numerical results, while significantly better than those provided by other state-of-art methods, for some networks show that differences between tested scenarios do not indicate any superior behavior when using game theoretic concepts; moreover, those obtained without using any selection for survival suggest that the search is actually guided by the inner mechanism of the extremal optimization method and by the fitness function used to evaluate and compare components within an individual.

Game theory models strategic and conflicting situations and offers several solution concepts that are known as game equilibria, among which the Nash equilibrium is probably the most popular one. A less known equilibrium, called the (k,t)-robust equilibrium, has recently been used in the context of distributed computing. The (k,t)-robust equilibrium combines the concepts of k-resiliency and t-immunity: a strategy profile is k-resilient if there is no coalition of k players that can benefit from improving their payoffs by collective deviation, and it is t-immune if any action of any t players does not decrease the payoffs of the others. A strategy profile is (k,t)-robust if it is both k-resilient and t-immune. In this paper an evolutionary approach of approximating (k,t)-robust equilibria is proposed. Numerical experiments are performed on a game that models node behavior in a distributed system.

Mixing Network Extremal Optimization is a new algorithm designed to identify the community structure in networks by using a game theoretic approach and a network mixing mechanism as a diversity preserving method. Numerical experiments performed on synthetic and real networks illustrate the potential of the approach.

The Berge-Zhukovskii equilibrium is an alternate solution concept in non-cooperative game theory that formalizes cooperation in a noncooperative setting. In this paper, the ϵ-Berge-Zhukovskii equilibrium is introduced and characterized by using a generative relation. The generative relation also provides a solution to the problem of computing the ϵ-Berge-Zhukovskii equilibrium for large games, by using evolutionary algorithms. Numerical examples illustrate the approach and provide a possible application for this equilibrium concept.

The Berge-Zhukovskii optimal Nash equilibrium combines the properties of the popular Nash equilibrium with the ones of the less known Berge-Zhukovskii by proposing yet another Nash equilibrium refinement. Moreover, a computational approach for the detection of these newly proposed equilibria is presented with examples for two auction games.

The problem of equilibria detection of a discrete-time Generalized Cournot Dynamic Oligopoly is approached by using a Differential Evolution and a Particle Swarm Optimization algorithm adapted to compute and track the set of generalized Nash equilibria in a dynamic setting. Both challenges of this problem, i.e. to correctly compute the entire set of generalized Nash equilibria of the constrained (generalized) game, and also to cope with the dynamic character of the landscape, are dealt with by using a simple adaptive mechanism. Numerical experiments for settings up to 60 players are performed to illustrate the efficiency of the approach.

Discrete-time dynamic games capture changes within game parameters (payoffs), representing thus a more realistic real-world decision model. A new approach to equilibria detection and tracking in a dynamic game setting, called Dynamic Equilibrium Tracking Differential Evolution, is proposed. A discrete-time dynamic asymmetric Cournot oligopoly is introduced and used to evaluate the proposed method by means of numerical experiments for instances up to 70 players. Results indicate the effectiveness and the potential of the proposed method.

In a mixed strategy equilibrium players randomize between their actions according to a very specific probability distribution, even though with regard to the game payoff, they are indifferent between their actions. Currently, there is no compelling model explaining why and how agents may randomize their decisions is such a way, in real world scenarios. In this paper we experiment with a model for bimatrix games, where the goal of the players is to find robust strategies for which the uncertainty in the outcome of the opponent is reduced as much as possible. We show that in an evolutionary setting, the proposed model converges to mixed strategy profiles, if these exist. The result suggest that only local knowledge of the game is sufficient to attain the adaptive convergence.

The aim of this paper is to asses simultaneous spectrum access situations that may occur in Cognitive Radio (CR) environments. The approach is that of one-shot, non-cooperative games describing CR interactions. Open spectrum access scenarios are modelled based on continuous and discrete reformulations of the Cournot game theoretical model. CR interaction situations are described by Nash and Pareto equilibria. Also, the heterogeneity of players is captured by the new concept of joint Nash-Pareto equilibrium, allowing CRs to be biased toward different types of equilibrium. Numerical simulations reveal equilibrium situations that may be reached in simultaneous access scenarios of two and three users.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player can deviate from the equilibrium strategy in order to increase her/his payoff. Some games can have several Nash equilibria. Strong Berge and strong Berge Pareto equilibria are important refinements of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge and strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player (agent) wants to deviate from the equilibrium strategy in order to increase the payoff. Some games can have more Nash equilibria. Several refinements have been developed. Strong Berge Pareto equilibrium is an important refinement of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

An evolutionary procedure based on nondomination with respect to the generative relation is proposed for detecting different new equilibria types. The notions of joint Pareto-Aumann, Aumann-Pareto, Nash-Aumann and Aumann-Nash equilibrium are introduced. These combinations (representing new solution concepts) may allow an approximation of how people play in real life situations. Some numerical experiments show the importance of this new equilibria types.

The problem of equilibria detection in many-player games is computationally untractable by standard techniques. Generative relations represent an useful tool for equilibria characterization and evolutionary equilibria detection. The generative relation for k-Berge-Zhukovskii equilibrium is introduced. An evolutionary technique based on differential evolution capable to cope with hundred players is proposed. Experimental results performed on a multi-player version of Prisoner’s Dilemma indicate the effectiveness of the approach.

Two important network system problems, the job scheduling, and the bin packing problem are presented from a game theoretical perspective. Solution concepts are related to Nash and Aumann equilibria. The concept of Aumann equilibrium is viewed from a different perspective. A generative relation of the Aumann equilibrium is considered. A generative relation is used for the evolutionary detection of the equilibrium. The numerical experiments demonstrate the effectiveness of the proposed method in addressing job scheduling and bin packing problems.

A generative relation for Aumann equilibrium is proposed. An evolutionary procedure based on nondomination with respect to the generative relation is used for detecting Aumann equilibrium.