检索结果-南通市图书馆

Bipartite-Oriented Distributed graph partitioning for Big Learning

在线全文

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2015年第1期30卷 20-29页

作者：陈榕施佳鑫陈海波臧斌宇 Shanghai Key Laboratory of Scalable Computing and Systems Institute of Parallel and Distributed Systems Shanghai Jiao Tong University Shanghai 200240 China

Many machine learning and data mining （MLDM] problems like recommendation, topic modeling, and medical diagnosis can be modeled as computing on bipartite graphs. However, inost distributed graph-parallel systems are oblivious to the unique characteristics in such graphs and existing online graph partitioning algorithms usually cause excessive repli- cation of vertices as well as significant pressure on network communication. This article identifies the challenges and oppor- tunities of partitioning bipartite graphs for distributed MLDM processing and proposes Bigraph, a set of bipartite-oriented graph partitioning algorithms. Bigraph leverages observations such as the skewed distribution of vertices, discriminated computation load and imbalanced data sizes between the two subsets of vertices to derive a set of optimal graph partition- ing algorithms that result in minimal vertex replication and network communication. Bigraph has been implemented on Powergraph and is shown to have a performance boost up to 17.75X （from 1.16X） for four typical MLDM algorithnls, due to reducing up to 80% vertex replication, and up to 96% network traffic.

关键词： bipartite graph graph partitioning graph-parallel system

A Reduced-Order Modeling of Multi-Port RC Networks by Means of graph partitioning

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Semiconductors 2002年第10期23卷 1037-1040页

作者：杨华中冒小建燕昭然汪蕙清华大学电子工程系北京100084

A modified reduced-order method for RC networks which takes a division-and-conquest strategy is *** whole network is partitioned into a set of sub-networks at first,then each of them is reduced by Krylov subspace techniques,and finally all the reduced sub-networks are incorporated *** some accuracy,this method can reduce the number of both nodes and components of the circuit comparing to the traditional methods which usually only offer a reduced net with less *** can markedly accelerate the sparse-matrix-based simulators whose performance is dominated by the entity of the matrix or the number of components of the circuits.

关键词： interconnect reduced-order modeling graph partitioning Krylov subspace

Dynamic airspace configuration method based on a weighted graph model

在线全文

学校读者我要写书评

暂无评论

Chinese Journal of Aeronautics 2014年第4期27卷 903-912页

作者： Chen Yangzhou Zhang Defu School of Electronic Information and Control Engineering Beijing University of Technology

This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent those key points such as airports, waypoints, and the edges represent those air routes. Those vertices are used as the sites of Voronoi diagram, which divides the airspace into units called as cells. Then, aircraft counts of both each cell and of each air-route are computed. Thus, by assigning both the vertices and the edges with those aircraft counts, a weighted graph model comes into being. Accordingly the airspace configuration problem is described as a weighted graph partitioning problem. Then, the problem is solved by a graph partitioning algorithm, which is a mixture of general weighted graph cuts algorithm, an optimal dynamic load balancing algorithm and a heuristic algorithm. After the cuts algorithm partitions the model into sub-graphs, the load balancing algorithm together with the heuristic algorithm transfers aircraft counts to balance workload among sub-graphs. Lastly, airspace configuration is completed by determining the sector boundaries. The simulation result shows that the designed sectors satisfy not only workload balancing condition, but also the constraints such as convexity, connectivity, as well as minimum distance constraint.

关键词： Airspace sector Air traffic control Dynamic airspace configuration graph partitioning graph theory Weighted graph Workload

Betweenness-based algorithm for a partition scale-free graph

在线全文

学校读者我要写书评

暂无评论

Chinese Physics B 2011年第11期20卷 556-564页

作者：张百达吴俊杰唐玉华周静 National Laboratory for Parallel and Distributed Processing School of ComputersNational University of Defense Technology Department of Computer Science and Technology School of ComputersNational University of Defense Technology

Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.

关键词： graph partitioning betweenness-based partitioning algorithm scale free network

Parallel hydrodynamic finite element model with an N-Best refining partition scheme

在线全文

学校读者我要写书评

暂无评论

Chinese Journal of Oceanology and Limnology 2010年第6期28卷 1340-1349页

作者：张振昌洪华生 WAI Onyx Winghong 江毓武周昌乐 Department of Computer Science Xiamen University State Key Laboratory of Marine Environmental Science(Xiamen University) Department of Civil and Structural Engineering the Hong Kong Polytechnic University

We enhance a robust parallel finite element model for coasts and estuaries cases with the use of N-Best refinement algorithms,in multilevel partitioning *** partitioning is an important step to construct the parallel model,in which computation speed is a big *** partitioning strategy includes the division of the research domain into several semi-equal-sized sub-domains,minimizing the sum weight of edges between different *** schemes for graph partitioning are divided into three phases:coarsening,partitioning,and *** the uncoarsening phase,many refinement algorithms have been proposed previously,such as KL,Greedy,and Boundary *** this study,we propose an N-Best refinement algorithm and show its advantages in our case study of Xiamen *** with original partitioning algorithm in previous models,the N-Best algorithm can speed up the computation by 1.9 times,and the simulation results are in a good match with the in-situ data.

关键词： N-Best graph partitioning parallel computation finite element method (FEM) domaindecomposition

Optimal Data Placement and Replication Approach for SIoT with Edge

在线全文

学校读者我要写书评

暂无评论

Computer Systems Science & Engineering 2022年第5期41卷 661-676页

作者： B.Prabhu Shankar S.Chitra Department of Information Technology Er Perumal Manimekalai College of EngineeringHosur635117TamilnaduIndia Department of Computer Science and Engineering Er Perumal Manimekalai College of EngineeringHosur63117TamilnaduIndia

Social networks(SNs)are sources with extreme number of users around the world who are all sharing data like images,audio,and video to their friends using IoT *** concept is the so-called Social Internet of Things(SIot).The evolving nature of edge-cloud computing has enabled storage of a large volume of data from various sources,and this task demands an efficient storage *** this kind of large volume of data storage,the usage of data replication using edge with geo-distributed cloud service area is suited to fulfill the user’s expectations with low *** major issue is the way to store the data and replicate these large data items optimally and allocate the request from the data center *** efficient storage of these data,we use edge server,which is part of the cloud server,in this ***,the data are distributed and stored with quick access,which will reduce the latency with *** proposed data placement approach learns with machine learning(ML)algorithm called radial basis kernel function assisted with support vector machine(RBF-SVM)to classify the data center for storing the user and friend’s data from the SIoT *** learning algorithms will be used to predict the workload of the data stored in the data center as either edge or cloud depending on the existing time *** data placement with dynamic nature is also optimized using the proposed dynamic graph partitioning(GP)method to meet the individual user’s demand of low latency with minimum *** way will keep the SIoT data placement efficient and effective over ***,this proposed data placement and replication approach introduces three kinds of innovations compared with the existing data placement approach.(i)Rather than storing the user data in a single cloud,this study uses the edge server closest to the SIoT devices for faster access with reduced response time.(ii)The classification algorithm called RBF-SVM is used to find storage for

关键词： Data placement data replication social network social internet of things edge computing cloud computing graph partitioning support vector machine machine learning radial basis function latency storage cost

Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science in China(Series F) 2003年第6期46卷 459-465页

作者：杨华中胡冠章 Department of Electronic Engineering Tsinghua UniversityBeijing 100084China Department of Mathematical Science Tsinghua UniversityBeijing 100084China

The spectrum of a graph is the set of all eigenvalues of the Laplacian matrix of the graph. There is a closed relationship between the Laplacian spectrum of graphs and some properties of graphs such as connectivity. In the recent years Laplacian spectrum of graphs has been widely applied in many fields. The application of Laplacian spectrum of graphs to circuit partitioning problems is reviewed in this paper. A new criterion of circuit partitioning is proposed and the bounds of the partition ratio for weighted graphs are also presented. Moreover, the deficiency of graph-partitioning algorithms by Laplacian eigenvectors is addressed and an algorithm by means of the minimal spanning tree of a graph is proposed. By virtue of taking the graph structure into consideration this algorithm can fulfill general requirements of circuit partitioning.

关键词： graph partitioning Laplacian spectrum of a graph partition ratio spanning tree of a graph.

Dynamic airspace configuration by genetic algorithm

在线全文

学校读者我要写书评

暂无评论

Journal of Traffic and Transportation Engineering(English Edition) 2017年第3期4卷 300-314页

作者： Marina Sergeeva Daniel Delahaye Catherine Mancel Andrija Vidosavljevic Laboratory in Applied Mathematics Computer Science and Automatics for Air Transport Ecole Nationale de L'Aviation Civile Toulouse 31055 France

With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transportation system and air traffic management. In recent years, special interest has been paid to the solution of the dynamic airspace configuration problem. Airspace sector configurations need to be dynamically adjusted to provide maximum efficiency and flexibility in response to changing weather and traffic conditions. The main objective of this work is to automatically adapt the airspace configurations ac- cording to the evolution of traffic. In order to reach this objective, the airspace is considered to be divided into predefined 3D airspace blocks which have to be grouped or ungrouped depending on the traffic situation. The airspace structure is represented as a graph and each airspace configuration is created using a graph partitioning technique. We optimize airspace configurations using a genetic algorithm. The developed algorithm generates a sequence of sector configurations for one day of operation with the minimized controller workload. The overall methodology is implemented and successfully tested with air traffic data taken for one day and for several different airspace control areas of Europe.

关键词： Dynamic airspace configuration Genetic algorithm Sectorization graph partitioning

New Network Immunization Strategy ~tter than the EGP Strategy

在线全文

学校读者我要写书评

暂无评论

China Communications 2012年第5期9卷 90-99页

作者：牛长喜李乐民 School of Communication and Information Engineering University of Electronic Science and Technology of China

This paper aims at designing a better net-work i,,imozatopm strategy to fight against the Sus- ceptible-Infected-Susceptible （SIS） type epidemic spreading in networks. Previous work used the nurrber of drops in the spectral radius of the net-work for evaluation and guiding the design of im-munization strategies. Instead, we propose using the infected node number in the steady state of SIS spreading as the appropriate metric. We use the metric to point out the limitations of the Equal graph partitioning （EGP） strategy and the ＂max-△λ＂ strategy, which are two representative network inmmnization strategies, and then identify the criti-cal role of epidemic spreading parameters in the e-valuation and design of network immuzization strat- egies. Based on all of these, we design a new immuzization strategy. Simulation results show that our strategy performs consistently better than the EGP strategy. In many cases, it uses only 50% less re-sources to achieve the same immuzization effect.

关键词： network security epidemic networkimmunization strategy graph partitioning spectralradius