Search

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem. [ABSTRACT FROM AUTHOR]

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency. [ABSTRACT FROM AUTHOR]

The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence. [ABSTRACT FROM AUTHOR]

Rooted triplets are becoming one of the most important types of input for reconstructing rooted phylogenies. A rooted triplet is a phylogenetic tree on three leaves and shows the evolutionary relationship of the corresponding three species. In this paper, we investigate the problem of inferring the maximum consensus evolutionary tree from a set of rooted triplets. This problem is known to be APX-hard. We present two new heuristic algorithms. For a given set of m triplets on n species, the FastTree algorithm runs in O(m + α(n)n²) time, where α(n) is the functional inverse of Ackermann's function. This is faster than any other previously known algorithms, although the outcome is less satisfactory. The Best Pair Merge with Total Reconstruction (BPMTR) algorithm runs in O(mn³) time and, on average, performs better than any other previously known algorithms for this problem. [ABSTRACT FROM AUTHOR]

Network caching is a technique used to speed-up user access to frequently requested contents in complex data networks. This paper presents a two-layer overlay network caching system for content distribution. It is used to define some caching scenarios with increasing complexity, which refers to real situations, including mobile 5G connectivity. For each scenario our aim is to maximize the hit ratio, which leads to the formulation of NP-complete optimization problems. The heuristic solutions proposed are based on the theory of the maximization of monotone submodular functions under matroid constraints. After the determination of the approximation ratio of the greedy heuristic algorithms proposed, a numerical performance analysis is shown. This analysis includes a comparison with the Least-Frequently Used (LFU) eviction strategy adapted to the analyzed systems. Results show very good performance, under the hypotheses of either known or unknown popularity of contents. [ABSTRACT FROM AUTHOR]

Integrated information theory (IIT) proposes a measure of integrated information, termed Phi (Φ), to capture the level of consciousness of a physical system in a given state. Unfortunately, calculating Φ itself is currently possible only for very small model systems and far from computable for the kinds of system typically associated with consciousness (brains). Here, we considered several proposed heuristic measures and computational approximations, some of which can be applied to larger systems, and tested if they correlate well with Φ. While these measures and approximations capture intuitions underlying IIT and some have had success in practical applications, it has not been shown that they actually quantify the type of integrated information specified by the latest version of IIT and, thus, whether they can be used to test the theory. In this study, we evaluated these approximations and heuristic measures considering how well they estimated the Φ values of model systems and not on the basis of practical or clinical considerations. To do this, we simulated networks consisting of 3–6 binary linear threshold nodes randomly connected with excitatory and inhibitory connections. For each system, we then constructed the system's state transition probability matrix (TPM) and generated observed data over time from all possible initial conditions. We then calculated Φ, approximations to Φ, and measures based on state differentiation, coalition entropy, state uniqueness, and integrated information. Our findings suggest that Φ can be approximated closely in small binary systems by using one or more of the readily available approximations (r > 0.95) but without major reductions in computational demands. Furthermore, the maximum value of Φ across states (a state-independent quantity) correlated strongly with measures of signal complexity (LZ, rs = 0.722), decoder-based integrated information (Φ*, rs = 0.816), and state differentiation (D1, rs = 0.827). These measures could allow for the efficient estimation of a system's capacity for high Φ or function as accurate predictors of low- (but not high-)Φ systems. While it is uncertain whether the results extend to larger systems or systems with other dynamics, we stress the importance that measures aimed at being practical alternatives to Φ be, at a minimum, rigorously tested in an environment where the ground truth can be established. [ABSTRACT FROM AUTHOR]