A Semi-Supervised WLAN Indoor Localization Method Based on l1-Graph Algorithm

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.

Totally Coded Method for Signal Flow Graph Algorithm

After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algorithm. The code-series (CS) have the holo-information nature, so that both the content and the sign of each gain-term can be determined via the coded method. The principle of this method is simple and it is suited for computer programming. The capability of the computer-aided analysis for switched current network (SIN) can be enhanced.

A Sharding Scheme Based on Graph Partitioning Algorithm for Public Blockchain

Blockchain technology,with its attributes of decentralization,immutability,and traceability,has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes.However,transaction performance and scalability has become the main challenges hindering the widespread adoption of blockchain.Due to its inability to meet the demands of high-frequency trading,blockchain cannot be adopted in many scenarios.To improve the transaction capacity,researchers have proposed some on-chain scaling technologies,including lightning networks,directed acyclic graph technology,state channels,and shardingmechanisms,inwhich sharding emerges as a potential scaling technology.Nevertheless,excessive cross-shard transactions and uneven shard workloads prevent the sharding mechanism from achieving the expected aim.This paper proposes a graphbased sharding scheme for public blockchain to efficiently balance the transaction distribution.Bymitigating crossshard transactions and evening-out workloads among shards,the scheme reduces transaction confirmation latency and enhances the transaction capacity of the blockchain.Therefore,the scheme can achieve a high-frequency transaction as well as a better blockchain scalability.Experiments results show that the scheme effectively reduces the cross-shard transaction ratio to a range of 35%-56%and significantly decreases the transaction confirmation latency to 6 s in a blockchain with no more than 25 shards.

Algorithm for Visualization of Zero Divisor Graphs of the Ring ℤn Using MAPLE Coding

This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict relationships between elements of a ring that multiply to zero. The paper explores the development and implementation of algorithms in MAPLE for constructing these ZDGs. The comparative study aims to discern the strengths, limitations, and computational efficiency of different MAPLE algorithms for creating zero divisor graphs offering insights for mathematicians, researchers, and computational enthusiasts involved in ring theory and mathematical computations.

基于改进GraphSAGE算法的浏览器指纹追踪

当前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算法对浏览器指纹长期追踪的能力。

Formal Derivation of Graph AlgorithmicPrograms Using Partition-and-Recur

In this paper, we derive, by presenting some suitable notations, three typical graph aLgorithms and corresponding programs using a unified approach, partition-and-recur. We putemphasis on the derivation rather than the algorithms themselves. The main ideas and lugesnutty of these algorithms are revealed by formula deduction. Success in these examples givesus more evidence that partition-and-recur is a simple and practical approach and developingenough suitable notations is the key in designing and deriving efficient and correct algorithmicprograms.

Evolutionary Graph Drawing Algorithms

In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.

Edge Crossing Minimization Algorithm for Hierarchical Graphs Based on Genetic Algorithms

We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following advantages: the frame of the algorithms is unified, the method is simple, and its implementation and revision are easy.

An effective multi-level algorithm based on ant colony optimization for graph bipartitioning

Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration （VLSI） design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant＇s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute （ANSI） C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.

CONVERGENCE ANALYSIS AND MRALLEL IMPLEMENTION FOR THE DIRECTEDGRAPH -ALGORITHM

In this paper we discuss the convergence of the directed graph-algorithm for solving a kind of optimization problems where the objective and subjective functions are all separable, and the parallel implementation process for the directed graph -algorithm is introduced.

A Graph Drawing Algorithm for Visualizing Multivariate Categorical Data

In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.

A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs

The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.

Dual-stage constructed random graph algorithm to generate random graphs featuring the same topological characteristics with power grids

It is a common practice to simulate some historical or test systems to validate the efficiency of new methods or concepts. However, there are only a small number of existing power system test cases, and validation and evaluation results, obtained using such a limited number of test cases, may not be deemed sufficient or convincing. In order to provide more available test cases, a new random graph generation algorithm, named ‘‘dualstage constructed random graph’’ algorithm, is proposed to effectively model the power grid topology. The algorithm generates a spanning tree to guarantee the connectivity of random graphs and is capable of controlling the number of lines precisely. No matter how much the average degree is,whether sparse or not, random graphs can be quickly formed to satisfy the requirements. An approach is developed to generate random graphs with prescribed numbers of connected components, in order to simulate the power grid topology under fault conditions. Our experimental study on several realistic power grid topologies proves that the proposed algorithm can quickly generate a large number of random graphs with the topology characteristics of real-world power grid.

Jointly-check iterative decoding algorithm for quantum sparse graph codes

For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation （BP） algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.

Algorithm for Fast Calculation of Hirzebruch-Jung Continued Fraction Expansions to Coding of Graph Manifolds

We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, which we used to simulate the coupling constant hierarchy for the universe with five fundamental interactions. Moreover, we can explicitly compute the integer Laplacian block matrix associated with any tree plumbing graph. This matrix coincides up to sign with the integer linking matrix (the main topological invariant) of the graph manifold corresponding to the plumbing graph. The need for a special algorithm appeared during computations of these topological invariants of complicated graph manifolds since there emerged a set of special rational numbers (fractions) with huge numerators and denominators;for these rational numbers, the ordinary methods of expansion in continued fraction became unusable.

The Refinement Algorithm Consideration in Text Clustering Scheme Based on Multilevel Graph

To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of clustering algorithm has to be improved with the refinement algorithm application. The experiment result demonstrated that the multilevel graph text clustering algorithm is available. Key words text clustering - multilevel coarsen graph model - refinement algorithm - high-dimensional clustering CLC number TP301 Foundation item: Supported by the National Natural Science Foundation of China (60173051)Biography: CHEN Jian-bin(1970-), male, Associate professor, Ph. D., research direction: data mining.

Design and Implementation of NBA Playoff Prediction Method Based on ELO Algorithm and Graph Database

With the globalization of NBA, all eyes on the NBA playoffs are around the world. Ones celebrate the winning of their team which they like. Especially, NBA fans keep on predicting the playoffs game results. However, prediction of winning probability of teams in NBA playoffs is challenging. In order to meet the challenges, we proposed a method using ELO algorithm for prediction and leveraging Graph Database, Neo4j, for implementation. Experiment results show that, the design and implementation of the prediction system could work to some degree.

An O(n) Time Algorithm for Scheduling UET-UCT of Bipartite Digraphs of Depth One on Two Processors

Given n unit execution time (UET) tasks whose precedence constraints form a directed acyclic graph, the arcs are associated with unit communication time (UCT) delays. The problem is to schedule the tasks on two identical processors in order to minimize the makespan. Several polynomial algorithms in the literature are proposed for special classes of digraphs, but the complexity of solving this problem in general case is still a challenging open question. We present in this paper an O(n) time algorithm to compute an optimal schedule for the class of bipartite digraphs of depth one.

Betweenness-based algorithm for a partition scale-free graph

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.