Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investme...Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investments required to deploy these networks, particularly related to the cost of equipment (optical fibers, transponders and multiplexers), the optimization of bandwidth and dynamic allocation of resources is essential to control operating costs and ensure continuity of service. Automatic switching technology for optical networks brings intelligence to the control plane to fully facilitate bandwidth utilization, traffic redirection, and automatic configuration of end-to-end services. This paper considers a local network operator’s WDM network without the implementation of the automatic switching technology, develops a network modeling software platform called Graphic Networks and using graph theory integrates a particularity of the automatic switching technology, which is the automatic rerouting of traffic in case of incident in the network. The incidents considered here are those links or route failures and node failures.展开更多
For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be colle...For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be collected in offline phase. Therefore,collecting training data with positioning information is time consuming which becomes the bottleneck of WLAN indoor localization. In this paper,the traditional semisupervised learning method based on k-NN and ε-NN graph for reducing collection workload of offline phase are analyzed,and the result shows that the k-NN or ε-NN graph are sensitive to data noise,which limit the performance of semi-supervised learning WLAN indoor localization system. Aiming at the above problem,it proposes a l1-graph-algorithm-based semi-supervised learning( LG-SSL) indoor localization method in which the graph is built by l1-norm algorithm. In our system,it firstly labels the unlabeled data using LG-SSL and labeled data to build the Radio Map in offline training phase,and then uses LG-SSL to estimate user's location in online phase. Extensive experimental results show that,benefit from the robustness to noise and sparsity ofl1-graph,LG-SSL exhibits superior performance by effectively reducing the collection workload in offline phase and improving localization accuracy in online phase.展开更多
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...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.展开更多
First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computat...First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold.展开更多
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of node...This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.展开更多
With the widespread application of distributed systems, many problems need to be solved urgently. How to design distributed optimization strategies has become a research hotspot. This article focuses on the solution r...With the widespread application of distributed systems, many problems need to be solved urgently. How to design distributed optimization strategies has become a research hotspot. This article focuses on the solution rate of the distributed convex optimization algorithm. Each agent in the network has its own convex cost function. We consider a gradient-based distributed method and use a push-pull gradient algorithm to minimize the total cost function. Inspired by the current multi-agent consensus cooperation protocol for distributed convex optimization algorithm, a distributed convex optimization algorithm with finite time convergence is proposed and studied. In the end, based on a fixed undirected distributed network topology, a fast convergent distributed cooperative learning method based on a linear parameterized neural network is proposed, which is different from the existing distributed convex optimization algorithms that can achieve exponential convergence. The algorithm can achieve finite-time convergence. The convergence of the algorithm can be guaranteed by the Lyapunov method. The corresponding simulation examples also show the effectiveness of the algorithm intuitively. Compared with other algorithms, this algorithm is competitive.展开更多
当前Web追踪领域主要使用浏览器指纹对用户进行追踪。针对浏览器指纹追踪技术存在指纹随时间动态变化、不易长期追踪等问题,提出一种关注节点和边缘特征的改进图采样聚合算法(An Improved Graph SAmple and AGgregatE with Both Node an...当前Web追踪领域主要使用浏览器指纹对用户进行追踪。针对浏览器指纹追踪技术存在指纹随时间动态变化、不易长期追踪等问题,提出一种关注节点和边缘特征的改进图采样聚合算法(An Improved Graph SAmple and AGgregatE with Both Node and Edge Features,NE-GraphSAGE)用于浏览器指纹追踪。首先以浏览器指纹为节点、指纹之间特征相似度为边构建图数据。其次对图神经网络中的GraphSAGE算法进行改进使其不仅能关注节点特征,而且能捕获边缘信息并对边缘分类,从而识别指纹。最后将NE-GraphSAGE算法与Eckersley算法、FPStalker算法和LSTM算法进行对比,验证NE-GraphSAGE算法的识别效果。实验结果表明,NE-GraphSAGE算法在准确率和追踪时长上均有不同程度的提升,最大追踪时长可达80天,相比其他3种算法性能更优,验证了NE-GraphSAGE算法对浏览器指纹长期追踪的能力。展开更多
This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core...This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core of this mining system are four sets of parallel graphmining algorithms programmed in the BSP parallel model and one set of data extractiontransformationload ing （ETE） algorithms implemented in MapReduce. To invoke these algorithm sets, we designed a workflow engine which optimized for cloud computing. Finally, a welldesigned data management function enables users to view, delete and input data in the Ha doop distributed file system （HDFS）. Experiments on artificial data show that the components of graphmining algorithm in MBGM are efficient.展开更多
We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minim...We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.展开更多
文摘Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investments required to deploy these networks, particularly related to the cost of equipment (optical fibers, transponders and multiplexers), the optimization of bandwidth and dynamic allocation of resources is essential to control operating costs and ensure continuity of service. Automatic switching technology for optical networks brings intelligence to the control plane to fully facilitate bandwidth utilization, traffic redirection, and automatic configuration of end-to-end services. This paper considers a local network operator’s WDM network without the implementation of the automatic switching technology, develops a network modeling software platform called Graphic Networks and using graph theory integrates a particularity of the automatic switching technology, which is the automatic rerouting of traffic in case of incident in the network. The incidents considered here are those links or route failures and node failures.
基金Sponsored by the National Natural Science Foundation of China(Grant No.61101122)the National High Technology Research and Development Program of China(Grant No.2012AA120802)the National Science and Technology Major Project of the Ministry of Science and Technology of China(Grant No.2012ZX03004-003)
文摘For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be collected in offline phase. Therefore,collecting training data with positioning information is time consuming which becomes the bottleneck of WLAN indoor localization. In this paper,the traditional semisupervised learning method based on k-NN and ε-NN graph for reducing collection workload of offline phase are analyzed,and the result shows that the k-NN or ε-NN graph are sensitive to data noise,which limit the performance of semi-supervised learning WLAN indoor localization system. Aiming at the above problem,it proposes a l1-graph-algorithm-based semi-supervised learning( LG-SSL) indoor localization method in which the graph is built by l1-norm algorithm. In our system,it firstly labels the unlabeled data using LG-SSL and labeled data to build the Radio Map in offline training phase,and then uses LG-SSL to estimate user's location in online phase. Extensive experimental results show that,benefit from the robustness to noise and sparsity ofl1-graph,LG-SSL exhibits superior performance by effectively reducing the collection workload in offline phase and improving localization accuracy in online phase.
基金supported by the National Science Foundation for Distinguished Young Scholars of China(Grant Nos.61003082 and 60903059)the National Natural Science Foundation of China(Grant No.60873014)the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(Grant No.60921062)
文摘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.
文摘First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold.
基金This research is supported by National Natural Science Foundation(70471042)
文摘This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.
文摘With the widespread application of distributed systems, many problems need to be solved urgently. How to design distributed optimization strategies has become a research hotspot. This article focuses on the solution rate of the distributed convex optimization algorithm. Each agent in the network has its own convex cost function. We consider a gradient-based distributed method and use a push-pull gradient algorithm to minimize the total cost function. Inspired by the current multi-agent consensus cooperation protocol for distributed convex optimization algorithm, a distributed convex optimization algorithm with finite time convergence is proposed and studied. In the end, based on a fixed undirected distributed network topology, a fast convergent distributed cooperative learning method based on a linear parameterized neural network is proposed, which is different from the existing distributed convex optimization algorithms that can achieve exponential convergence. The algorithm can achieve finite-time convergence. The convergence of the algorithm can be guaranteed by the Lyapunov method. The corresponding simulation examples also show the effectiveness of the algorithm intuitively. Compared with other algorithms, this algorithm is competitive.
文摘当前Web追踪领域主要使用浏览器指纹对用户进行追踪。针对浏览器指纹追踪技术存在指纹随时间动态变化、不易长期追踪等问题,提出一种关注节点和边缘特征的改进图采样聚合算法(An Improved Graph SAmple and AGgregatE with Both Node and Edge Features,NE-GraphSAGE)用于浏览器指纹追踪。首先以浏览器指纹为节点、指纹之间特征相似度为边构建图数据。其次对图神经网络中的GraphSAGE算法进行改进使其不仅能关注节点特征,而且能捕获边缘信息并对边缘分类,从而识别指纹。最后将NE-GraphSAGE算法与Eckersley算法、FPStalker算法和LSTM算法进行对比,验证NE-GraphSAGE算法的识别效果。实验结果表明,NE-GraphSAGE算法在准确率和追踪时长上均有不同程度的提升,最大追踪时长可达80天,相比其他3种算法性能更优,验证了NE-GraphSAGE算法对浏览器指纹长期追踪的能力。
基金supported by ZTE Industry-Academia-Research Cooperaton Funds
文摘This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core of this mining system are four sets of parallel graphmining algorithms programmed in the BSP parallel model and one set of data extractiontransformationload ing （ETE） algorithms implemented in MapReduce. To invoke these algorithm sets, we designed a workflow engine which optimized for cloud computing. Finally, a welldesigned data management function enables users to view, delete and input data in the Ha doop distributed file system （HDFS）. Experiments on artificial data show that the components of graphmining algorithm in MBGM are efficient.
文摘We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.
