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

algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality

INFORMATION PROCESSING LETTERS 2024年 183卷

作者： Wang, Shanshan Xiao, Chenglong Casseau, Emmanuel Shantou Univ Shantou Peoples R China Univ Rennes IRISA CNRS INRIA Rennes France

The problem of enumerating all connected induced subgraphs of a given order kfrom a given graph arises in many practical applications: bioinformatics, information retrieval, processor design, to name a few. The upper bound on the number of connected induced subgraphs of order kis n center dot (e Delta)(k) /( Delta-1)k, where Delta is the maximum degree in the input graph Gand nis the number of vertices in G. In this short communication, we first introduce a new neighborhood operator that is the key to design reverse search algorithms for enumerating all connected induced subgraphs of order k. Based on the proposed neighborhood operator, three algorithms with delay of O(k center dot min{(n - k), k Delta} center dot (k log Delta + logn)), O(k center dot min{(n - k), k Delta} center dot n) and O(k(2) center dot min{(n - k), k Delta} center dot min{k, Delta}) respectively are proposed. The first two algorithms require exponential space to improve upon the current best delay bound O(k(2) Delta)[4] for this problem in the case k > nlog Delta-logn- Delta+root nlognlog Delta log Delta and k > n(2) /n+ Delta respectively.

关键词： graph algorithms Subgraph enumeration Connected induced subgraphs Reverse search

来源：评论

学校读者我要写书评

暂无评论

WICO graph: A Labeled Dataset of Twitter Subgraphs based on Conspiracy Theory and 5G-Corona Misinformation Tweets 13

WICO Graph: A Labeled Dataset of Twitter Subgraphs based on ...

引用

13th International Conference on Agents and Artificial Intelligence (ICAART)

作者： Schroeder, Daniel Thilo Schaal, Ferdinand Filkukova, Petra Pogorelov, Konstantin Langguth, Johannes Simula Metropolitan Ctr Digital Engn Oslo Norway Tech Univ Berlin Berlin Germany Tech Univ Denmark Lyngby Denmark Simula Res Lab Fornebu Norway

ISBN: (纸本)9789897584848

In the wake of the COVID-19 pandemic, a surge of misinformation has flooded social media and other internet channels, and some of it has the potential to cause real-world harm. To counteract this misinformation, reliably identifying it is a principal problem to be solved. However, the identification of misinformation poses a formidable challenge for language processing systems since the texts containing misinformation are short, work with insinuation rather than explicitly stating a false claim, or resemble other postings that deal with the same topic ironically. Accordingly, for the development of better detection systems, it is not only essential to use hand-labeled ground truth data and extend the analysis with methods beyond Natural Language Processing to consider the characteristics of the participant's relationships and the diffusion of misinformation. This paper presents a novel dataset that deals with a specific piece of misinformation: the idea that the 5G wireless network is causally connected to the COVID-19 pandemic. We have extracted the subgraphs of 3,000 manually classified Tweets from Twitter's follower network and distinguished them into three categories. First, subgraphs of Tweets that propagate the specific 5G misinformation, those that spread other conspiracy theories, and Tweets that do neither. We created the WICO (Wireless Networks and Coronavirus Conspiracy) dataset to support experts in machine learning experts, graph processing, and related fields in studying the spread of misinformation. Furthermore, we provide a series of baseline experiments using both graph Neural Networks and other established classifiers that use simple graph metrics as features. The dataset is available at https://***/wico-graph..

关键词： graph Neural Networks graph algorithms Misinformation Fake-News Detection

来源：评论

学校读者我要写书评

暂无评论

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut 63

The Quantum and Classical Streaming Complexity of Quantum an...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Kallaugher, John Parekh, Ojas Sandia Natl Labs POB 5800 Albuquerque NM 87185 USA

ISBN: (纸本)9781665455190

We investigate the space complexity of two graph streaming problems: MAX-CUT and its quantum analogue, QUANTUM MAX-CUT. Previous work by Kapralov and Krachun [STOC '19] resolved the classical complexity of the classical problem, showing that any (2 - epsilon)-approximation requires Omega(n) space (a 2-approximation is trivial with O(log n) space). We generalize both of these qualifiers, demonstrating Omega(n) space lower bounds for (2-epsilon)-approximatingMAX-CUT and QUANTUM MAX-CUT, even if the algorithm is allowed to maintain a quantum state. As the trivial approximation algorithm for QUANTUM MAX-CUT only gives a 4-approximation, we show tightness with an algorithm that returns a (2 + epsilon)-approximation to the QUANTUM MAX-CUT value of a graph in O(log n) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using o(n) space. We prove our lower bounds through the techniques of Boolean Fourier analysis. We give the first application of these methods to sequential one-way quantum communication, in which each player receives a quantum message from the previous player, and can then perform arbitrary quantum operations on it before sending it to the next. To this end, we show how Fourier-analytic techniques may be used to understand the application of a quantum channel.

关键词： quantum algorithms graph algorithms streaming algorithms fourier analysis

来源：评论

学校读者我要写书评

暂无评论

Anomaly based Incident Detection in Large Scale Smart Transportation Systems 13

Anomaly based Incident Detection in Large Scale Smart Transp...

引用

13th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS )

作者： Islam, Md Jaminur Talusan, Jose Paolo Bhattacharjee, Shameek Tiausas, Francis Vazirizade, Sayyed Mohsen Dubey, Abhishek Yasumoto, Keiichi Das, Sajal K. Western Michigan Univ Kalamazoo MI 49008 USA Nara Inst Sc & Tech Nara Japan Vanderbilt Univ 221 Kirkland Hall Nashville TN 37235 USA Missouri Univ Sci & Technol Rolla MO 65409 USA

ISBN: (纸本)9781665409674

Modern smart cities are focusing on smart transportation solutions to detect and mitigate the effects of various traffic incidents in the city. To materialize this, roadside units and ambient transportation sensors are being deployed to collect vehicular data that provides real-time traffic monitoring. In this paper, we first propose a real-time data-driven anomaly-based traffic incident detection framework for a city-scale smart transportation system. Specifically, we propose an incremental region growing approximation algorithm for optimal Spatio-temporal clustering of road segments and their data;such that road segments are strategically divided into highly correlated clusters. The highly correlated clusters enable identifying a Pythagorean Mean-based invariant as an anomaly detection metric that is highly stable under no incidents but shows a deviation in the presence of incidents. We learn the bounds of the invariants in a robust manner such that anomaly detection can generalize to unseen events, even when learning from real noisy data. We perform extensive experimental validation using mobility data collected from the City of Nashville, Tennessee, and prove that the method can detect incidents within each cluster in real-time.

关键词： Unsupervised Learning Anomaly Detection Smart Transportation graph algorithms Cluster Analysis Regression Incident Detection

来源：评论

学校读者我要写书评

暂无评论

Factorial Lower Bounds for (Almost) Random Order Streams 63

Factorial Lower Bounds for (Almost) Random Order Streams

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Chiplunkar, Ashish Kallaugher, John Kapralov, Michael Price, Eric IIT Delhi Delhi India Sandia Natl Labs Albuquerque NM 87185 USA Ecole Polytech Fed Lausanne Lausanne Switzerland UT Austin Austin TX USA

ISBN: (纸本)9781665455190

In this paper we introduce and study the STREAMINGCYCLES problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph G, comprising n/l disjoint length-l cycles on n vertices, are partitioned randomly among n players. Every edge is annotated with an independent uniformly random bit, and the players' task is to output, for some cycle in G, the sum (modulo 2) of the bits on its edges, after one round of sequential communication. Our main result is an l(Omega(l)) lower bound on the communication complexity of STREAMINGCYCLES, which is tight up to constant factors in the exponent. Applications of our lower bound for STREAMINGCYCLES include an essentially tight lower bound for component collection in (almost) random order graph streams, making progress towards a conjecture of Peng and Sohler [SODA'18] and the first exponential space lower bounds for random walk generation.

关键词： streaming algorithms graph algorithms fourier analysis communication complexity

来源：评论

学校读者我要写书评

暂无评论

graph Iso/Auto-morphism: A Divide-&-Conquer Approach 21

Graph Iso/Auto-morphism: A Divide-&-Conquer Approach

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Lu, Can Yu, Jeffrey Xu Zhang, Zhiwei Cheng, Hong Chinese Univ Hong Kong Hong Kong Peoples R China Beijing Inst Technol Beijing Peoples R China

ISBN: (纸本)9781450383431

graph isomorphism is to determine whether two graphs are isomorphic. A closely related problem is graph automorphism (symmetry) detection, where an isomorphism between two graphs is a bijection between their vertex sets that preserves adjacency, and an automorphism is an isomorphism from a graph to itself. By graph automorphism, we deal with symmetric subgraph matching (SSM), which is to find all subgraphs in a graph G that are symmetric to a given subgraph q in G. To test two graphs for isomorphism, canonical labeling has been studied to relabel a graph in such a way that isomorphic graphs are identical after relabeling. Efficient canonical labeling algorithms are designed by individualization-refinement. They enumerate all permutations using a search tree, and select the minimum one as the canonical labeling. These algorithms face difficulties in handling massive graphs, and the search trees used are for pruning purposes which cannot answer symmetric subgraphs matching. In this paper, we design a new efficient canonical labeling algorithm DviCL based on the observation that we can use the k-th minimum permutation as the canonical labeling. Different from previous algorithms, we take a divide-and-conquer approach to partition a graph G. By partitioning G, an AutoTree is constructed, which preserves symmetric structures as well as the automorphism group of G. The canonical labeling for a tree node can be obtained by composing those of its child nodes, and the canonical labeling for the root is the one for G. Such AutoTree can also be effectively used to answer the automorphism group and symmetric subgraphs. We conducted extensive performance studies using 22 large graphs, and confirmed that DviCL is much more efficient and robust than the state-of-the-art.

关键词： graph isomorphism graph automorphism graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Using dependency graph and graph theory concepts to identify anti-patterns in a microservices system: A tool-based approach 7

Using dependency graph and graph theory concepts to identify...

引用

Moratuwa Engineering Research Conference (MERCon) / 7th International Multidisciplinary Engineering Research Conference

作者： Gamage, Isuru Udara Piyadigama Perera, Indika Univ Moratuwa Dept Comp Sci & Engn Katubedda Sri Lanka

ISBN: (纸本)9781665437530

Microservice architecture (MSA) based application developments are becoming the common trend in implementing large-scale applications. Unlike the traditional monolith applications, MSA applications are composed of many services hence there is an immense possibility of anti-patterns introduced into the system. To identify these design problems, a detailed analysis of the architecture needs to be performed. We see great potential for adopting graph concepts and algorithms in this regard. However, the few tools proposed by existing work to find anti-patterns that adopt graph concepts are not up to providing developers with adequate statistical information such as metrics along with visualization techniques or they are not fully automated. In this research, we present a tool-based solution for this problem which is capable of utilizing traced data of an MSA system to generate dependency graphs and thereby extract metrics using graph theory concepts and algorithms. We analyze a sample MSA system for anti-patterns with the tool. To verify the usability of the tool further, a group of developers also analyze an open-source system with the tool.

关键词： Microservices Architecture evaluation Anti-patterns graph algorithms Dependency graph

来源：评论

学校读者我要写书评

暂无评论

A tight (1.5+ϵ)-approximation for unsplittable capacitated vehicle routing on trees

引用

MATHEMATICAL PROGRAMMING 2024年

作者： Mathieu, Claire Zhou, Hang CNRS Paris France Ecole Polytech Palaiseau France

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+& varepsilon;)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.

关键词： Approximation algorithms Capacitated vehicle routing graph algorithms Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A Heterogeneous Solution to the All-pairs Shortest Path Problem using FPGAs 23

A Heterogeneous Solution to the All-pairs Shortest Path Prob...

引用

23rd International Symposium on Quality Electronic Design (ISQED)

作者： Chirila, Mihnea D'Alberto, Paolo Ting, Hsin-Yu Veidenbaum, Alexander Nicolau, Alexandru Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

ISBN: (纸本)9781665494663

Heterogeneous systems present exciting new opportunities for graph and Machine Learning applications. This paper presents a novel approach for the All-pairs Shortest Path (APSP) computation using a heterogeneous CPU-FPGA Accelerator system. It is based on a recursive variant of Kleene's APSP algorithm. Carefully re-engineering the algorithm to exploit parallelism in both the Floyd-Warshall algorithm and the general Kleene algorithm to perform Floyd-Warshall and Matrix-Multiply on the FPGA while the CPU efficiently balances the communication and computation between the kernels, improves state-of-the-art performance on FPGAs for APSP, while achieving near-GPU levels of performance, with less power and hardware resources, and outperforms the CPU-only solution by over 137x for a 8192x8192 problem size. When adjusted for power draw differences in process nodes, it also surpasses the GPU implementation in terms of performance per Watt by over 13%.

关键词： FPGA heterogeneous computing graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance 62

Breaking the Cubic Barrier for (Unweighted) Tree Edit Distan...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Mao, Xiao MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

ISBN: (纸本)9781665420556

The (unweighted) tree edit distance problem for n node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in O(n(3)) time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007]. The same paper also showed that O(n(3)) is the best possible running time for any algorithm using the so-called decomposition strategy, which underlies almost all the known algorithms for this problem. These algorithms would also work for the weighted tree edit distance problem, which cannot be solved in truly sub-cubic time under the APSP conjecture [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. In this paper, we break the cubic barrier by showing an O(n(2.9546)) time algorithm for the unweighted tree edit distance problem. We consider an equivalent maximization problem and use a dynamic programming scheme involving matrices with many special properties. By using a decomposition scheme as well as several combinatorial techniques, we reduce tree edit distance to the max-plus product of bounded-difference matrices, which can be solved in truly sub-cubic time [Bringmann, Grandoni, Saha, and Vassilevska Williams, FOCS 2016].

关键词： fine-grained complexity graph algorithms tree edit distance min-plus product

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：