Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This st...Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This study addresses this gap by developing specialized incremental SCC detection methods.We first leverage distinct edge types inherent in citation graphs to devise partition and local topological ordering strategies,minimizing redundant graph traversals.Based on this,we introduce two efficient bounded incremental algorithms:one for continuous single updates via dynamic maintenance of partitions and order,and the other for batch updates that further reduces edge traversals by building upon the single-update technique.Experimental evaluations on real-world citation graphs verify significant efficiency improvements,with our single incremental method achieving speedups of at least 11.5 times,and the batch incremental method achieving speedups of at least 5.0 times compared with baseline methods.展开更多
The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study propose...The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study proposes a DP algorithm based on node block sequence constraints.The proposed algorithm constrains the traversal process of the parent graph by using the M-sequence matrix to considerably reduce the time consumption and space complexity by pruning the traversal process of the order graph using the node block sequence.Experimental results show that compared with existing DP algorithms,the proposed algorithm can obtain learning results more efficiently with less than 1%loss of accuracy,and can be used for learning larger-scale networks.展开更多
Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a rev...Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.61925203 and U22B2021.
文摘Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This study addresses this gap by developing specialized incremental SCC detection methods.We first leverage distinct edge types inherent in citation graphs to devise partition and local topological ordering strategies,minimizing redundant graph traversals.Based on this,we introduce two efficient bounded incremental algorithms:one for continuous single updates via dynamic maintenance of partitions and order,and the other for batch updates that further reduces edge traversals by building upon the single-update technique.Experimental evaluations on real-world citation graphs verify significant efficiency improvements,with our single incremental method achieving speedups of at least 11.5 times,and the batch incremental method achieving speedups of at least 5.0 times compared with baseline methods.
基金Shaanxi Science Fund for Distinguished Young Scholars,Grant/Award Number:2024JC-JCQN-57Xi’an Science and Technology Plan Project,Grant/Award Number:2023JH-QCYJQ-0086+2 种基金Scientific Research Program Funded by Education Department of Shaanxi Provincial Government,Grant/Award Number:P23JP071Engineering Technology Research Center of Shaanxi Province for Intelligent Testing and Reliability Evaluation of Electronic Equipments,Grant/Award Number:2023-ZC-GCZX-00472022 Shaanxi University Youth Innovation Team Project。
文摘The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study proposes a DP algorithm based on node block sequence constraints.The proposed algorithm constrains the traversal process of the parent graph by using the M-sequence matrix to considerably reduce the time consumption and space complexity by pruning the traversal process of the order graph using the node block sequence.Experimental results show that compared with existing DP algorithms,the proposed algorithm can obtain learning results more efficiently with less than 1%loss of accuracy,and can be used for learning larger-scale networks.
文摘Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.
