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

Efficiently Computing Maximum Clique of Sparse graphs with Many-Core graphical Processing Units

学校读者我要写书评

暂无评论

Efficiently Computing Maximum Clique of Sparse Graphs with M...

19th International Conference on Software Technologies, ICSOFT 2024

作者： Cardone, Lorenzo Di Martino, Salvatore Quer, Stefano Politecnico di Torino Turin Italy

ISBN: (纸本)9789897587061

The Maximum Clique is a fundamental problem in graph theory and has numerous applications in various domains. The problem is known to be NP-hard, and even the most efficient algorithm requires significant computational resources when applied to medium or large graphs. To obtain substantial acceleration and improve scalability, we enable highly parallel computations by proposing a many-core graphical processing unit implementation targeting large and sparse real-world graphs. We developed our algorithm from CPUbased solvers, redesigned the graph preprocessing step, introduced an alternative parallelization scheme, and implemented block-level and warp-level parallelism. We show that the latter performs better when the amount of threads included in a block cannot be fully exploited. We analyze the advantages and disadvantages of the proposed strategy and its behavior on different graph topologies. Our approach, applied to sparse real-world graph instances, shows a geomean speed-up of 9x, an average speed-up of over 19x, and a peak speed-up of over 70x, compared to a parallel implementation of the BBMCSP algorithm. It also obtains a geometric mean speed-up of 1.21x and an average speed-up of over 2.0x on the same graph instances compared to the parallel implementation of the LMC algorithm. © 2024 by SCITEPRESS – Science and Technology Publications, Lda.

关键词： graph algorithms

The Smith normal form of the Q-walk matrix of the Dynkin graph An

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jia, Yaning Pan, Shengyong School of Mathematics and Statistics Beijing Jiaotong University Beijing100044 China

In this paper, we give an explicit formula for the rank of the Q-walk matrix of the Dynkin graph An. Moreover, we prove that its Smith normal form is diag ( (1|, 2 r= _{z_2 ⌈ ,_ n2 ..., ⌉ _2}, 0, ..., 0 ) ), where r i... 详细信息

关键词： graph algorithms

Efficient Kernelization Algorithm for Bipartite graph Matching

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wu, Guang Gan, Xinbiao Pang, Zhengbin Huang, Bo Ran, Bopin National University of Defence Technology College of Computer Science and Technology China

Finding the maximum matching in bipartite graphs is a fundamental graph operation widely used in various fields. To expedite the acquisition of the maximum matching, Karp and Sipser introduced two data reduction rules aimed at decreasing the input size. However, the KaSi algorithm, which implements the two data reduction rules, has several drawbacks: a high upper bound on time complexity and inefficient storage structure. The poor upper bound on time complexity makes the algorithm lack robustness when dealing with extreme cases, and the inefficient storage structure struggles to balance vertex merging and neighborhood traversal operations, leading to poor performance on real-life graphs. To address these issues, we introduced MVM, an algorithm incorporating three novel optimization strategies to implement the data reduction rules. Our theoretical analysis proves that the MVM algorithm, even when using data structures with the worst search efficiency, can still maintain near-linear time complexity, ensuring the algorithm’s robustness. Additionally, we designed an innovative storage format that supports efficient vertex merging operations while preserving the locality of edge sets, thus ensuring the efficiency of neighborhood traversals in graph algorithms. Finally, we conduct evaluations on both real-life and synthetic graphs. Extensive experiments demonstrate the superiority of our method. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

USING WEAKEST APPLICATION CONDITIONS TO RANK graph TRANSFORMATIONS FOR graph REPAIR

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fritsche, Lars Lauer, Alexander Kratz, Maximilian Schürr, Andy Taentzer, Gabriele Technical University Darmstadt Darmstadt Germany Philipps-Universität Marburg Marburg Germany

When using graphs and graph transformations to model systems, consistency is an important concern. While consistency has primarily been viewed as a binary property, i.e., a graph is consistent or inconsistent with respect to a set of constraints, recent work has presented an approach to consistency as a graduated property. This allows living with inconsistencies for a while and repairing them when necessary. For repairing inconsistencies in a graph, we use graph transformation rules with so-called impairment-indicating and repair-indicating application conditions to understand how much repair gain certain rule applications would bring. Both types of conditions can be derived from given graph constraints. Our main theorem shows that the difference between the number of actual constraint violations before and after a graph transformation step can be characterized by the difference between the numbers of violated impairment-indicating and repair-indicating application conditions. This theory forms the basis for algorithms with look-ahead that rank graph transformations according to their potential for graph repair. An evaluation shows that graph repair can be well supported by rules with these new types of application conditions in terms of effectiveness and scalability. This paper provides further theoretical results and an extended evaluation of the results presented in [FLST24].MSC Codes 68R10 © 2024, CC BY-SA.

关键词： graph algorithms

Human-Centric Community Detection in Hybrid Metaverse Networks with Integrated AI Entities 25

学校读者我要写书评

暂无评论

Human-Centric Community Detection in Hybrid Metaverse Networ...

34th ACM Web Conference, WWW 2025

作者： Chiu, Shih-Hsuan Teng, Ya-Wen Yang, De-Nian Chen, Ming-Syan National Taiwan University Taipei Taiwan Academia Sinica Taipei Taiwan

ISBN: (纸本)9798400712746

Community detection is a cornerstone problem in social network analysis (SNA), aimed at identifying cohesive communities with minimal external links. However, the rise of generative AI and Metaverse introduce complexities by creating hybrid human-AI social networks (denoted by HASNs), where traditional methods fall short, especially in human-centric settings. This paper introduces a novel community detection problem in HASNs (denoted by MetaCD), which seeks to enhance human connectivity within communities while reducing the presence of AI nodes. Effective processing of MetaCD poses challenges due to the delicate trade-off between excluding certain AI nodes and maintaining community structure. To address this, we propose CUSA, an innovative framework incorporating AI-aware clustering techniques that navigate this trade-off by selectively retaining AI nodes that contribute to community integrity. Furthermore, given the scarcity of real-world HASNs, we devise four strategies for synthesizing these networks under various hypothetical scenarios. Empirical evaluations on real social networks, reconfigured as HASNs, demonstrate the effectiveness and practicality of our approach compared to traditional non-deep learning and graph neural network (GNN)-based methods. © 2025 Copyright held by the owner/author(s).

关键词： graph algorithms

Online Network Inference from graph-Stationary Signals with Hidden Nodes

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Buciulea, Andrei Navarro, Madeline Rey, Samuel Segarra, Santiago Marques, Antonio G. Dept. of Signal Theory and Communications Rey Juan Carlos University Madrid Spain Dept. of Electrical and Computer Engineering Rice University HoustonTX United States

graph learning is the fundamental task of estimating unknown graph connectivity from available data. Typical approaches assume that not only is all information available simultaneously but also that all nodes can be observed. However, in many real-world scenarios, data can neither be known completely nor obtained all at once. We present a novel method for online graph estimation that accounts for the presence of hidden nodes. We consider signals that are stationary on the underlying graph, which provides a model for the unknown connections to hidden nodes. We then formulate a convex optimization problem for graph learning from streaming, incomplete graph signals. We solve the proposed problem through an efficient proximal gradient algorithm that can run in real-time as data arrives sequentially. Additionally, we provide theoretical conditions under which our online algorithm is similar to batch-wise solutions. Through experimental results on synthetic and real-world data, we demonstrate the viability of our approach for online graph learning in the presence of missing observations. © 2024, CC BY.

关键词： graph algorithms

Fast Computation for the Forest Matrix of an Evolving graph

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sun, Haoxin Zhou, Xiaotian Zhang, Zhongzhi Shanghai Key Laboratory of Intelligent Information Processing School of Computer Science Fudan University Shanghai200433 China

The forest matrix plays a crucial role in network science, opinion dynamics, and machine learning, offering deep insights into the structure of and dynamics on networks. In this paper, we study the problem of querying entries of the forest matrix in evolving graphs, which more accurately represent the dynamic nature of real-world networks compared to static graphs. To address the unique challenges posed by evolving graphs, we first introduce two approximation algorithms, SFQ and SFQPlus, for static graphs. SFQ employs a probabilistic interpretation of the forest matrix, while SFQPlus incorporates a novel variance reduction technique and is theoretically proven to offer enhanced accuracy. Based on these two algorithms, we further devise two dynamic algorithms centered around efficiently maintaining a list of spanning converging forests. This approach ensures O(1) runtime complexity for updates, including edge additions and deletions, as well as for querying matrix elements, and provides an unbiased estimation of forest matrix entries. Finally, through extensive experiments on various real-world networks, we demonstrate the efficiency and effectiveness of our algorithms. Particularly, our algorithms are scalable to massive graphs with more than forty million nodes. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

Settling the Pass Complexity of Approximate Matchings in Dynamic graph Streams

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Assadi, Sepehr Behnezhad, Soheil Konrad, Christian Naidu, Kheeran K. Sundaresan, Janani Cheriton School of Computer Science University of Waterloo Canada Khoury College of Computer Sciences Northeastern University United States School of Computer Science University of Bristol United Kingdom

A semi-streaming algorithm in dynamic graph streams processes any n-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O(n · polylog(n)) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds: • We present a randomized sketching based semi-streaming algorithm for O(1)-approximation of maximum matching in dynamic streams using O(log log n) passes. The approximation ratio of this algorithm can be improved to (1 + Ε) for any fixed Ε > 0 even on weighted graphs using standard techniques. This exponentially improves upon several O(log n) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. • We prove that any semi-streaming algorithm (not only sketching based) for O(1)-approximation of maximum matching in dynamic streams requires Ω(log log n) passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area. © 2024, CC BY.

关键词： graph algorithms

Finding the Center and Centroid of a graph with Multiple Sources

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chou, Matthew

We consider the problem of finding a "fair" meeting place when S people want to get together. Specifically, we will consider the cases where a "fair" meeting place is defined to be either 1) a node on a graph that minimizes the maximum time/distance to each person or 2) a node on a graph that minimizes the sum of times/distances to each of the sources. In graph theory, these nodes are denoted as the center and centroid of a graph respectively. In this paper, we propose a novel solution for finding the center and centroid of a graph by using a multiple source alternating Dijkstra’s Algorithm. Additionally, we introduce a stopping condition that significantly saves on time complexity without compromising the accuracy of the solution. The results of this paper are a low complexity algorithm that is optimal in computing the center of S sources among N nodes and a low complexity algorithm that is close to optimal for computing the centroid of S sources among N nodes. © 2024, CC BY.

关键词： graph algorithms