To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approxima...To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approximates the densest k-subgraphs of the entire graph through four steps:partitioning the large-scale dynamic graph,constructing a partial set of the densest k-subgraphs,heuristically merging the subgraph sets,and finally extracting the densest k-subgraphs.This approach significantly reduces the computational time for large-scale dynamic graphs while simultaneously improving the quality of the resulting subgraphs.This algorithm is applicable to various definitions of“density”and can accommodate diverse requirements on the number of edges.When integrated with existing static densest subgraph detection algorithms,it achieves scalability and computational efficiency.Theoretical analysis demonstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9.To evaluate the performance of the algorithm,experiments were conducted on four billion-scale datasets:Friendster,Orkut,YouTube,and DBLP.The results indicate that the proposed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.展开更多
State constraints in nonlinear systems are commonly pursued by resorting to barrier functions,which enforce constraints over the entire duration of system operation.We propose a universal intermittent state-constraine...State constraints in nonlinear systems are commonly pursued by resorting to barrier functions,which enforce constraints over the entire duration of system operation.We propose a universal intermittent state-constrained solution,which not only offers flexibility by activating constraints just during specific time periods of interest to the user,but also successfully accommodates different types of constraint boundaries.The innovative shifting functions are proposed to facilitate seamless transitions between constrained and unconstrained operational phases,resulting in more user-friendly design and implementation.By blending an improved shifting transformation into intermittent constraint design,we construct a universal barrier function upon the constrained states,with which our control strategy removes the limitations on constraint functions and completely obviates the feasibility conditions.Furthermore,a modified fuzzy approximator driven by the prediction error rather than the tracking error achieves decoupling of the control and estimation loops,which not only ensures the estimation performance,but also facilitates proof of stability.Finally,the effectiveness of the proposed scheme is assessed by numerical simulation.展开更多
基金The National Natural Science Foundation of China(No.62172443).
文摘To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs,this paper proposes a heuristic approximation algorithm.The algorithm approximates the densest k-subgraphs of the entire graph through four steps:partitioning the large-scale dynamic graph,constructing a partial set of the densest k-subgraphs,heuristically merging the subgraph sets,and finally extracting the densest k-subgraphs.This approach significantly reduces the computational time for large-scale dynamic graphs while simultaneously improving the quality of the resulting subgraphs.This algorithm is applicable to various definitions of“density”and can accommodate diverse requirements on the number of edges.When integrated with existing static densest subgraph detection algorithms,it achieves scalability and computational efficiency.Theoretical analysis demonstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9.To evaluate the performance of the algorithm,experiments were conducted on four billion-scale datasets:Friendster,Orkut,YouTube,and DBLP.The results indicate that the proposed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.
基金supported by the Fundamental Research Funds for the Central Universities(N2404005)the National Key Research and Development Program of China(2018YFA0702200)+2 种基金Liaoning Revitalization Talents Program(XLYC1801005)the National Natural Science Foundation of China(U23B20118)the Nature Science Foundation of Liaoning Province of China(2022JH25/10100008)。
文摘State constraints in nonlinear systems are commonly pursued by resorting to barrier functions,which enforce constraints over the entire duration of system operation.We propose a universal intermittent state-constrained solution,which not only offers flexibility by activating constraints just during specific time periods of interest to the user,but also successfully accommodates different types of constraint boundaries.The innovative shifting functions are proposed to facilitate seamless transitions between constrained and unconstrained operational phases,resulting in more user-friendly design and implementation.By blending an improved shifting transformation into intermittent constraint design,we construct a universal barrier function upon the constrained states,with which our control strategy removes the limitations on constraint functions and completely obviates the feasibility conditions.Furthermore,a modified fuzzy approximator driven by the prediction error rather than the tracking error achieves decoupling of the control and estimation loops,which not only ensures the estimation performance,but also facilitates proof of stability.Finally,the effectiveness of the proposed scheme is assessed by numerical simulation.
