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

25th International Conference on Web Information Systems Engineering, WISE 2024

作者： Hasegawa, Tsuyoshi Hironaka, Shiori Shudo, Kazuyuki Kyoto University Yoshida-nihonmatsu-cho Kyoto Sakyo-ku606-8501 Japan

ISBN: (纸本)9789819605668

Using random walks for sampling has proven advantageous in assessing the characteristics of large and unknown social networks. Several algorithms based on random walks have been introduced in recent years. In the practical application of social network sampling, there is a recurrent reliance on an application programming interface (API) for obtaining adjacent nodes. However, owing to constraints related to query frequency and associated API expenses, it is preferable to minimize API calls during the feature estimation process. In this study, considering the acquisition of neighboring nodes as a cost factor, we introduce a feature estimation algorithm that outperforms existing algorithms in terms of accuracy. Through experiments that simulate sampling on known graphs, we demonstrate the superior accuracy of our proposed algorithm when compared to existing alternatives. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The Par Clusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable graph Clustering 51st

The Par Clusterers Benchmark Suite (PCBS): A Fine-Grained An...

引用

51st International Conference on Very Large Data Bases, VLDB 2025

作者： Yu, Shangdi Shi, Jessica Meindl, Jamison Eisenstat, David Ju, Xiaoen Tavakkol, Sasan Dhulipala, Laxman Lącki, Jakub Mirrokni, Vahab Shun, Julian MIT United States Google United States UMD United States

We introduce the Par Clusterers Benchmark Suite (PCBS)—a collection of highly scalable parallel graph clustering algorithms and benchmarking tools that streamline comparing different graph clustering algorithms and implementations. The benchmark includes clustering algorithms that target a wide range of modern clustering use cases, including community detection, classification, and dense sub graph mining. The benchmark toolkit makes it easy to run and evaluate multiple instances of different clustering algorithms with respect to both the running time and quality. We evaluate the PCBS algorithms empirically and find that they deliver both the state of the art quality and the running time. Interms of the running time, they are on average over 4x faster than the fastest library we compared to. In terms of quality, the correlation clustering algorithm [Shi et al., VLDB’21] optimizing for the Lambda CC objective, which does not have a direct counter part in other libraries, delivers the highest quality in the majority of datasets that we used. © 2025, VLDB Endowment, All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The Complexity of graph Exploration Games 50th

The Complexity of Graph Exploration Games

引用

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Fuchs, Janosch Grüne, Christoph Janßen, Tom Department of Computer Science RWTH Aachen University Aachen Germany

ISBN: (纸本)9783031826962

graph Exploration problems ask a searcher to explore an unknown environment. The environment is modeled as a graph, where the searcher needs to visit each vertex beginning at some vertex. Treasure Hunt problems are a variation of graph Exploration, in which the searcher needs to find a hidden treasure, which is located at a designated vertex. Usually these problems are modeled as online problems, and any online algorithm performs poorly because it has too little knowledge about the instance to react adequately to the requests of the adversary. Thus, the impact of a priori knowledge is of interest. One form of a priori knowledge is an unlabeled map, which is an isomorphic copy of the graph. We analyze graph Exploration and Treasure Hunt problems with an unlabeled map that is provided to the searcher. For this, we formulate decision variants of both problems by interpreting the online problems as a game between the online algorithm (the searcher) and the adversary. The map, however, is not controllable by the adversary. The question is whether the searcher is able to explore the graph completely or find the treasure for all possible decisions of the adversary. We analyze these games in multiple settings, with and without costs on the edges, on directed and undirected graphs and with different constraints (allowing multiple visits to vertices or edges) on the solution. We prove PSPACE-completeness for most of these games. Additionally, we analyze the complexity of related problems that have additional constraints on the solution. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Linear-Time graph Programs without Preconditions 14

Linear-Time Graph Programs without Preconditions

引用

14th and 15th International Workshop on graph Computation Models, GCM 2023 and 2024

作者： Alaoui, Ziad Ismaili Plump, Detlef Department of Computer Science University of Liverpool Liverpool United Kingdom Department of Computer Science University of York York United Kingdom

We report on a recent breakthrough in rule-based graph programming, which allows us to reach the time complexity of imperative linear-time algorithms. In general, achieving the complexity of graph algorithms in conventional languages using graph transformation rules is challenging due to the cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be executed in linear time using the graph programming language GP 2. However, for non-destructive algorithms that retain the structure of input graphs, achieving linear runtime required input graphs to be connected and of bounded node degree. In this paper, we overcome these preconditions by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. We present three case studies, a cycle detection program, a program for numbering the connected components of a graph, and a breadth-first search program. Each of these programs runs in linear time on both connected and disconnected input graphs with arbitrary node degrees. We give empirical evidence for the linear time complexity by using timings for various classes of input graphs. © Z. Ismaili Alaoui & D. Plump.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Vectorized Sequence-to-graph Alignment Algorithm 24th

A Vectorized Sequence-to-Graph Alignment Algorithm

引用

24th International Conference on algorithms and Architectures for Parallel Processing, ICA3PP 2024

作者： Peng, Chenchen Tang, Shengbo Guo, Yifei Xia, Zeyu Yang, Canqun Cui, Yingbo College of Computer Science National University of Defense Technology Changsha China National Supercomputer Center in Tianjin Tianjin China Haihe Lab of ITAI Tianjin China

ISBN: (纸本)9789819615247

A pangenome graph can represent the genomes of multiple individuals simultaneously. It provides a more comprehensive reference and overcomes the allele bias caused by linear reference genome, which is becoming a powerful new source of information in research. Sequence-to-graph alignment is the computational core of many pangenome related tasks, which aligns sequences to a graph to find the best matches. It serves as a crucial link for upstream and downstream research applications. However, existing sequence-to-graph alignment algorithms can not handle large-scale sequences efficiently. In this paper, we propose a vectorization version of sequence-to-graph alignment algorithm. We vectorize the core of Gwfa with SIMD instructions to improve the speed of per sequence alignment. Experiments on real and simulated datasets showed that, our algorithm achieved speedups of about 1.5×, while maintaining the alignment result consistent. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic Variance-Reduced Iterative Hard Thresholding in graph Sparsity Optimization 24

Stochastic Variance-Reduced Iterative Hard Thresholding in G...

引用

8th International Conference on Computer Science and Artificial Intelligence, CSAI 2024

作者： Fox, Derek Hernandez, Samuel Tong, Qianqian UNCG GreensboroNC United States Texas A&M University College StationTX United States

ISBN: (纸本)9798400718182

Stochastic optimization algorithms are widely used for large-scale data analysis due to their low per-iteration costs, but they often suffer from slow asymptotic convergence caused by inherent variance. Variance-reduced techniques have been therefore used to address this issue in structured sparse models utilizing sparsity-inducing norms or 0-norms. However, these techniques are not directly applicable to complex (non-convex) graph sparsity models, which are essential in applications like disease outbreak monitoring and social network analysis. In this paper, we introduce two stochastic variance-reduced gradient-based methods to solve graph sparsity optimization: graphSVRG-IHT and graphSCSG-IHT. We provide a general framework for theoretical analysis, demonstrating that our methods enjoy a linear convergence speed. Extensive experiments validate the efficiency and effectiveness of our proposed algorithms. © 2024 Copyright held by the owner/author(s).

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

DYTC:Dynamic graph Triangle Counting on GPU 24

DYTC:Dynamic Graph Triangle Counting on GPU

引用

8th International Conference on algorithms, Computing and Systems, ICACS 2024

作者： Wang, Zhuo Li, Zhixiong Tu, Jinxing Huang, Jianqiang Department of Computer Technology and Applications Qinghai University Xining China Intelligent Computing and Application Laboratory of Qinghai Province Qinghai University Xining China

ISBN: (纸本)9798400718304

Triangle counting is a critical problem in graph theory and network analysis, with widespread applications in social network analysis, network science, and bioinformatics. Dynamic graphs are extensively utilized in various domains and are prevalent in real-world scenarios. Over time, dynamic graphs necessitate frequent updates, where vertices and edges are inserted, deleted, or modified. However, existing dynamic graph analysis methods often focus solely on the data structure of dynamic graphs, neglecting the algorithms for dynamic graph processing. Current triangle counting methods are typically designed for static graphs and are not suited for continuously updated dynamic graphs. In this paper, we propose an incremental triangle counting algorithm tailored for dynamic graphs, which only requires recomputing the affected subgraph caused by updated edges, rather than the entire graph. Consequently, in comparison to the previous algorithm, our algorithm is capable of attaining a maximum speedup of . © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Research on Adaptive Factor graph Fusion Perception Method for Transmission Line Crossing Under Multi Sensor Collaboration

Research on Adaptive Factor Graph Fusion Perception Method f...

引用

2024 International Conference on Mechatronics and Intelligent Control, ICMIC 2024

作者： Li, Yanfeng Yang, Yan Yang, Yanbin Dali Power Supply Bureau Yunnan Electric Power Corporation Dali671000 China

ISBN: (数字)9781510686847

ISBN: (纸本)9781510686830

The application of multi-sensor (millimeter wave radar, LiDAR, binocular camera, etc.) fusion perception technology to the monitoring of cross sections of transmission lines is proposed in response to the difficulty of defect elimination and repair after accidents in the critical section of "three spans".The factor graph model is constructed based on the transmission line status information collected by multiple sensors, and the fusion effect of multiple types of signals is achieved by integrating multi-sensor information variables and adopting a global optimization method to improve credibility. Through simulation, the information fusion effects of weighted average method, multi Bayesian estimation method, and factor graph algorithm were compared. The simulation results show that the factor graph algorithm has higher credibility and better performance in fusing multiple types of signals. It can maintain the stability of the system and enhance its robustness, thereby achieving the goal of accurate identification and warning of transmission line crossing safety risks and improving the safety operation level of the power grid. © 2025 SPIE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploring the Landscape of Distributed graph Sketching

Exploring the Landscape of Distributed Graph Sketching

引用

2025 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2025

作者： Tench, David West, Evan T. Zhang, Kenny Bender, Michael A. DeLayo, Daniel Farach-Colton, Martín Gill, Gilvir Seip, Tyler Zhang, Victor Lawrence Berkeley National Laboratory United States Stony Brook University United States Massachusetts Institute of Technology United States New York University United States MongoDB United States Meta Platforms United States

ISBN: (纸本)9798331311995

Recent work has initiated the study of dense graph processing using graph sketching methods, which drastically reduce space costs by lossily compressing information about the input graph. In this paper, we explore the strange and surprising performance landscape of sketching algorithms. We highlight both their surprising advantages for processing dense graphs that were previously prohibitively expensive to study, as well as the current limitations of the technique. Most notably, we show how sketching can avoid bottlenecks that limit conventional graph processing methods. Single-machine streaming graph processing systems are typically bottlenecked by CPU performance, and distributed graph processing systems are typically bottlenecked by network latency. We present Landscape, a distributed graph-stream processing system that uses linear sketching to distribute the CPU work of computing graph properties to distributed workers with no need for worker-to-worker communication. As a result, it overcomes the CPU and network bottlenecks that limit other systems. In fact, for the connected components problem, Landscape achieves a stream ingestion rate one-fourth that of maximum sustained RAM bandwidth, and is four times faster than random access RAM bandwidth. Additionally, we prove that for any sequence of graph updates and queries Landscape consumes at most a constant factor more network bandwidth than is required to receive the input stream. We show that this system can ingest up to 332 million stream updates per second on a graph with 217 vertices. We show that it scales well with more distributed compute power: given a cluster of 40 distributed worker machines, it can ingest updates 35 times as fast as with 1 distributed worker machine. graph sketching algorithms tend to incur high computational costs when answering queries;to address this Landscape uses heuristics to reduce its query latency by up to four orders of magnitude over the prior state of the art. Copyright ©

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for disaster-resilience augmentation of planar straight-line graphs

引用

JOURNAL OF GLOBAL OPTIMIZATION 2025年 1-26页

作者： Westcott, Alexander Ras, Charl Univ Melbourne Sch Math & Stat Parkville Australia

We consider the problem of adding a minimum length set of edges to a geometric graph so that the resultant graph is resilient against partition from the effect of a single disaster. Disasters are modeled by discs of given maximum radius, and a disaster destroys all edges intersecting its interior. It is assumed that the input and output graphs are planar with a straight-line embedding. We provide a computationally simple characterisation of feasible input instances in terms of the convex hull of the given graph, and present a fast ILP algorithm for generating optimal solutions. We also perform a computational study which shows that our algorithm is able to solve randomly generated instances with hundreds of nodes.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：