Search

The influence maximization problem aims to identify a set of starting nodes in a social network that can generate the highest possible spread of influence under a given diffusion model. In real-world scenarios, however, the emphasis is usually on budgeted influence maximization, which considers the expenses involved in activating users. The existing techniques struggle to balance node costs and influence and cannot optimally leverage the network's structural information. To address these problems, we propose a structure-aware dual probability evolutionary adaptive (SADPEA) algorithm that considers network structures and node cost. This innovative algorithm integrates advanced graph representation learning techniques, dual probability mutation evolutionary algorithms, and dual-candidate pool adaptive simulated annealing algorithms. By leveraging graph representation learning algorithms, we can expertly map network nodes to low-dimensional vectors, effectively capturing their structural information and relationships. This hybrid approach optimizes the balance between node influence and cost by selectively filtering nodes based on their initial costs. Our method was tested on six real-world social networks of varying scales and types and was compared to seven baseline algorithms. Our approach consistently outperformed the others, demonstrating an impressive balance between efficiency and solution quality. [ABSTRACT FROM AUTHOR]

In a typical wireless telecommunication network, a large number of communication links is established with a limited number of available frequencies. The problem that addresses assigning available frequencies to transmitters such that interference is avoided as far as possible is called the frequency assignment problem. The problem is usually modeled as a graph coloring (labeling) problem. We study in this paper the (s, t)-relaxed L(2, 1)-labeling of a graph which considers the situation where transceivers that are very close receive frequencies that differ by at least two while transceivers that are close receive frequencies that differ by at least one. In addition, the model allows at most s(resp. t) anomalies at distance one (resp. two). The objective of the model is to minimize the span of frequencies in a corresponding network. We show that it is NP-complete to decide whether the minimal span of a (1, 0)-relaxed L(2, 1)-labeling of a graph is at most k. We also prove that the minimal span of this labeling for two classes of graphs is bounded above with the the square of the largest degree in the graph of interest. These results confirm Conjecture 6 and partially confirm Conjecture 3 stated in Lin [J. Comb. Optim.31(2016) 1–22].

The star k-edge-coloring of graph Gis a proper edge coloring using kcolors such that no path or cycle of length four is bichromatic. The minimum number kfor which Gadmits a star k-edge-coloring is called the star chromatic index of G, denoted by χ′s(G). Let GCD(n, k) be the greatest common divisor of nand k. In this paper, we give a necessary and sufficient condition of χ′s(P(n, k)) = 4 for a generalized Petersen graph P(n, k) and show that “almost all” generalized Petersen graphs have a star 5-edge-colorings. Furthermore, for any two integers kand n(≥2k+ 1) such that GCD(n, k) ≥ 3, P(n, k) has a star 5-edge-coloring, with the exception of the case that GCD(n, k) = 3, k≠ GCD(n, k) and n3≡1(mod3){n \over 3} \equiv 1\left( {\bmod 3} \right).

The decision-making process, which is regarded as cognitive and ubiquitous, has been exploited in diverse fields, such as psychology, economics, and artificial intelligence. This paper considers the problem of modeling agent cognition in a class of game-theoretic decision-making scenarios called extensive games. We present a novel framework in which artificial neural networks are incorporated to simulate agent cognition regarding the structure of the underlying game and the goodness of the game situations therein. An algorithmic procedure is investigated to describe the process for solving games with cognition, and then, a new equilibrium concept is proposed as a refinement of the classical one—subgame perfect equilibrium—by involving players’ cognitive reasoning. Moreover, a series of results concerning the computational complexity, soundness, and completeness of the algorithm, as well as the existence of an equilibrium solution, is obtained. This framework, which is shown to be general enough to model the way in which AlphaGo plays Go, may offer a means for bridging the gap between theoretical models and practical problem-solving. [ABSTRACT FROM AUTHOR]