检索结果-内蒙古大学图书馆

Link Prediction Based on Node Centrality Measure 12th

学校读者我要写书评

暂无评论

Link Prediction Based on Node Centrality Measure

12th International Conference on Frontiers of Intelligent Computing: Theory and Applications, FICTA 2024

作者： Nandini, Y.V. Jaya Lakshmi, T. Enduri, Murali Krishna Algorithms and Complexity Theory Lab Department of Computer Science and Engineering SRM University-AP Andhra Pradesh Amaravati India Department of Computing Sheffield Hallam University Sheffield United Kingdom

ISBN: (纸本)9789819601424

Predicting links is crucial task for determining future links in complex networks across different real-world domains like information networks, social interactions, and technological networks. The link prediction method utilizes graph topological features to locate common neighborhood, yet it overlooks the importance of nodes within the network. In this context, we seek to utilize the importance of node in the network in the link prediction techniques. Centrality metrics measure a node’s relative importance within the network and demonstrates a strong correlation with future links in complex networks. In our study, we propose a novel link prediction measure called Local-Similarity based on Summation of Degree Centrality (CLP). CLP finds similarity scores for node pairs by considering common neighbors and use the centrality scores of these common neighbors in the prediction task. To assess our approach, we compare it with existing methods like Jaccard coefficient, Preferential Attachment, and a recent measure like Keyword Network Link Prediction based on degree centrality. We conduct experiments on four real-world datasets, and CLP shows significant improvements. On average, there’s a 15% improvement in Area Under the Receiver Operating Characteristic (AUROC) compared to existing methods and a 27% improvement over the recent one. Additionally, there’s an average 20 and 23% enhancement in Area Under Precision Recall (AUPR) compared to existing and recent methods. Our experiments highlight the superior performance of the proposed CLP method. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： Prediction models

Breaking Symmetries in Quantified Graph Search: A Comparative Study

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Janota, Mikoláš Kirchweger, Markus Peitl, Tomáš Szeider, Stefan Czech Technical University in Prague Czech Republic Algorithms and Complexity Group TU Wien Austria

Graph generation and enumeration problems often require handling equivalent graphs—those that differ only in vertex labeling. We study how to extend SAT Modulo Symmetries (SMS), a framework for eliminating such redundant graphs, to handle more complex constraints. While SMS was originally designed for constraints in propositional logic (in NP), we now extend it to handle quantified Boolean formulas (QBF), allowing for more expressive specifications like non-3-colorability (a coNP-complete property). We develop two approaches: a static QBF encoding and a dynamic method integrating SMS into QBF solvers. Our analysis reveals that while specialized approaches can be faster, QBF-based methods offer easier implementation and formal verification capabilities. © 2025, CC BY-NC-ND.

关键词： Formal verification

Tackling the α-Domination Problem Heuristically

学校读者我要写书评

暂无评论

Tackling the α-Domination Problem Heuristically

19th International Conference on Computer Aided Systems Theory, EUROCAST 2024

作者： Iurlano, Enrico Varga, Johannes Raidl, Günther R. Algorithms and Complexity Group TU Wien Favoritenstraße 9-11/192-01 Vienna1040 Austria

ISBN: (纸本)9783031829512

We focus on the α-domination problem, which is capable of modeling influence phenomena in social networks. It formally asks for a minimum cardinality subset of vertices of a given graph such that any vertex is either included in this subset or at least a fraction α of its neighbors is (0 © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Integer programming

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kaul, Matthias Luo, Kelin Mnich, Matthias Röglin, Heiko Universität Bonn Bonn Germany University at Buffalo New York United States Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We study the problem of partitioning a set of n objects in a metric space into k clusters V1, . . ., Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This setting has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial time algorithm computing a constant factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single p norm for the objective. © 2025, CC BY.

关键词： Trees (mathematics)

The Parameterized complexity Of Extending Stack Layouts 32

学校读者我要写书评

暂无评论

The Parameterized Complexity Of Extending Stack Layouts

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773430

An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial -page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations. © Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg.

关键词： Parameterization

The complexity of Optimizing Atomic Congestion 38

学校读者我要写书评

暂无评论

The Complexity of Optimizing Atomic Congestion

38th AAAI Conference on Artificial Intelligence, AAAI 2024

作者： Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Department of Computer Science and Engineering IIT Hyderabad India

ISBN: (纸本)1577358872

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies—that is, a centrally planned routing that minimizes the average cost of agents—is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. Copyright © 2024, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Computational complexity

A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Sridharan, Ramanujan M. Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria School of Computing DePaul University Chicago United States Department of Computer Science University of Warwick United Kingdom

We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R1, . . ., Rk positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R1, . . ., Rp, and ∈ . The problem is to decide if there is a serial schedule of at most moves (i.e., of makespan ) such that at the end of the schedule each robot with a destination reaches it, where a robot’s move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan . As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by for the special case of CSMP in which only a single robot has a destination and the graph is planar, which we prove to be NP-complete. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph. © 2025, CC BY-NC-ND.

关键词： Undirected graphs

Parameterized complexity of Feature Selection for Categorical Data Clustering 46

学校读者我要写书评

暂无评论

Parameterized Complexity of Feature Selection for Categorica...

46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772013

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k,B, |Σ|) mg(k,|Σ|) n2 for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental problems r

关键词： Budget control

Segment Intersection Representations, Level Planarity and Constrained Ordering Problems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fink, Simon D. Pfretzschner, Matthias Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University Prague Czech Republic Department of Applied Mathematics Charles University Prague Czech Republic

In the Segment Intersection Graph Representation Problem, we want to represent the vertices of a graph as straight line segments in the plane such that two segments cross if and only if there is an edge between the corresponding vertices. This problem is NP-hard (even ∃R-complete [19]) in the general case [13] and remains so if we restrict the segments to be axis-aligned, i.e., horizontal and vertical [12]. A long standing open question for the latter variant is its complexity when the order of segments along one axis (say the vertical order of horizontal segments) is already given [12,14]. We resolve this question by giving efficient solutions using two very different approaches that are interesting on their own. First, using a graph-drawing perspective, we relate the problem to a variant of the well-known Level Planarity problem, where vertices have to lie on preassigned horizontal levels. In our case, each level also carries consecutivity constraints on its vertices;this Level Planarity variant is known to have a quadratic solution. Second, we use an entirely combinatorial approach and show that both problems can equivalently be formulated as a linear ordering problem subject to certain consecutivity constraints. While the complexity of such problems varies greatly, we show that in this case the constraints are well-structured in a way that allows a direct quadratic solution. Thus, we obtain three different-but-equivalent perspectives on this problem: the initial geometric one, one from planar graph drawing and a purely combinatorial one. © 2025, CC BY.

关键词： Graph theory