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.

Event-Triggered Bipartite Consensus Tracking and Vibration Control of Flexible Timoshenko Manipulators Under Time-Varying Actuator Faults

For bipartite angle consensus tracking and vibration suppression of multiple Timoshenko manipulator systems with time-varying actuator faults,parameter and modeling uncertainties,and unknown disturbances,a novel distributed boundary event-triggered control strategy is proposed in this work.In contrast to the earlier findings,time-varying consensus tracking and actuator defects are taken into account simultaneously.In addition,the constructed event-triggered control mechanism can achieve a more flexible design because it is not required to satisfy the input-to-state condition.To achieve the control objectives,some new integral control variables are given by using back-stepping technique and boundary control.Moreover,adaptive neural networks are applied to estimate system uncertainties.With the proposed event-triggered scheme,control inputs can reduce unnecessary updates.Besides,tracking errors and vibration states of the closed-looped network can be exponentially convergent into some small fields,and Zeno behaviors can be excluded.At last,some simulation examples are given to state the effectiveness of the control algorithms.

Weak External Bisection of Some Graphs

Let G be a graph. A bipartition of G is a bipartition of V (G) with V (G) = V1 ∪ V2 and V1 ∩ V2 = ∅. If a bipartition satisfies ∥V1∣ - ∣V2∥ ≤ 1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott. The conjecture is that every graph G has a bisection (V1, V2) such that ∀v ∈ V1, at least half minuses one of the neighbors of v are in the V2;∀v ∈ V2, at least half minuses one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

Practical bipartite consensus for multi-agent systems:A barrier function-based adaptive sliding-mode control approach

This paper is concerned with bipartite consensus tracking for multi-agent systems with unknown disturbances.A barrier function-based adaptive sliding-mode control(SMC)approach is proposed such that the bipartite steady-state error is converged to a predefined region of zero in finite time.Specifically,based on an error auxiliary taking neighboring antagonistic interactions into account,an SMC law is designed with an adaptive gain.The gain can switch to a positive semi-definite barrier function to ensure that the error auxiliary is constrained to a predefined neighborhood of zero,which in turn guarantees practical bipartite consensus tracking.A distinguished feature of the proposed controller is its independence on the bound of disturbances,while the input chattering phenomenon is alleviated.Finally,a numerical example is provided to verify the effectiveness of the proposed controller.

Event-Triggered Asymmetric Bipartite Consensus Tracking for Nonlinear Multi-Agent Systems Based on Model-Free Adaptive Control

In this paper,an asymmetric bipartite consensus problem for the nonlinear multi-agent systems with cooperative and antagonistic interactions is studied under the event-triggered mechanism.For the agents described by a structurally balanced signed digraph,the asymmetric bipartite consensus objective is firstly defined,assigning the agents'output to different signs and module values.Considering with the completely unknown dynamics of the agents,a novel event-triggered model-free adaptive bipartite control protocol is designed based on the agents'triggered outputs and an equivalent compact form data model.By utilizing the Lyapunov analysis method,the threshold of the triggering condition is obtained.Subsequently,the asymptotic convergence of the tracking error is deduced and a sufficient condition is obtained based on the contraction mapping principle.Finally,the simulation example further demonstrates the effectiveness of the protocol.

Cycle Multiplicity of Total Graph of Complete Bipartite Graph

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].

The Evolving Bipartite Network and Semi-Bipartite Network Models with Adjustable Scale and Hybrid Attachment Mechanisms

The bipartite graph structure exists in the connections of many objects in the real world, and the evolving modeling is a good method to describe and understand the generation and evolution within various real complex networks. Previous bipartite models were proposed to mostly explain the principle of attachments, and ignored the diverse growth speed of nodes of sets in different bipartite networks. In this paper, we propose an evolving bipartite network model with adjustable node scale and hybrid attachment mechanisms, which uses different probability parameters to control the scale of two disjoint sets of nodes and the preference strength of hybrid attachment respectively. The results show that the degree distribution of single set in the proposed model follows a shifted power-law distribution when parameter r and s are not equal to 0, or exponential distribution when r or s is equal to 0. Furthermore, we extend the previous model to a semi-bipartite network model, which embeds more user association information into the internal network, so that the model is capable of carrying and revealing more deep information of each user in the network. The simulation results of two models are in good agreement with the empirical data, which verifies that the models have a good performance on real networks from the perspective of degree distribution. We believe these two models are valuable for an explanation of the origin and growth of bipartite systems that truly exist.

基于Web使用挖掘技术的聚类算法改进

Web使用挖掘中的聚类算法可以聚集相似特性的用户和页面,以便从中提取有用的感兴趣的信息。通过深入分析基于Hamming距离的聚类算法,指出其中存在的不合理性和低效性,然后根据这些不足引入了加权的bipartite图来表示整个数据集,修改了Hamming距离计算公式以便更准确地描述两对象间的相似度,并对算法进行了改进。实验结果表明,改进的算法是准确且高效的。

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.

Pilot Domain NOMA for Grant-Free Massive Random Access in Massive MIMO Marine Communication System

We propose a pilot domain non-orthogonal multiple access(NOMA)for uplink massive devices grant-free random access scenarios in massive multiple-input multiple-output(MIMO)maritime communication systems.These scenarios are characterized by numerous devices with sporadic access behavior,and therefore only a subset of them are active.Due to massive potential devices in the network,it is infeasible to assign a unique orthogonal pilot to each device in advance.In such scenarios,pilot decontamination is a crucial problem.In this paper,the devices are randomly assigned non-orthogonal pilots which are constructed by a linear combination of some orthogonal pilots.We show that a bipartite graph can conveniently describe the interference cancellation(IC)processes of pilot decontamination.High spectrum efficiency(SE)and low outage probability can be obtained by selecting the numbers of orthogonal pilots according to the given probability distribution.Numerical evaluatioDs show that the proposed pilot domain NOMA decreases the outage probability from 20%to 2 e-12 at the SE of 4 bits/s/Hz for a single device,compared to the conventional method of slotted ALOHA with 1024 antennas at the BS,or increases the spectrum efficiency from 1.2 bits/s/Hz to 4 bit/s/Hz at the outage probability of2 e-12 in contrast with the Welch bound equality(WBE)non-orthogonal pilots.

ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.

A quantitative analysis model of grid cyber physical systems

Conventional power systems are being developed into grid cyber physical systems(GCPS) with widespread application of communication, computer, and control technologies. In this article, we propose a quantitative analysis method for a GCPS. Based on this, we discuss the relationship between cyberspace and physical space, especially the computational similarity within the GCPS both in undirected and directed bipartite networks. We then propose a model for evaluating the fusion of the three most important factors: information, communication, and security. We then present the concept of the fusion evaluation cubic for the GCPS quantitative analysis model. Through these models, we can determine whether a more realistic state of the GCPS can be found by enhancing the fusion between cyberspace and physical space. Finally, we conclude that the degree of fusion between the two spaces is very important, not only considering the performance of the whole business process, but also considering security.

THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？

Secure Bipartite Tracking Control for Linear Leader-Following Multiagent Systems Under Denial-of-Service Attacks

Dear editor,This letter puts forward a secure feedback control scheme to bipartite tracking consensus for a set of generic linear autonomous agents subject to aperiodic and unknown denial-of-service(Do S)attacks.

Long-Term Effects of Recommendation on the Evolution of Online Systems

We employ a bipartite network to describe an online commercial system.Instead of investigating accuracy and diversity in each recommendation,we focus on studying the influence of recommendation on the evolution of the online bipartite network.The analysis is based on two benchmark datasets and several well-known recommendation algorithms.The structure properties investigated include item degree heterogeneity,clustering coefficient and degree correlation.This work highlights the importance of studying the effects and performance of recommendation in long-term evolution.

Quantum Correlations in a Family of Bipartite Qubit-Qutrit Separable States

Quantum correlations in a family of bipartite separable qubit-qutrit quantum-classical correlated states are investigated by using two popular measures,i.e.,the original quantum discord(OQD)method by Ollivier and Zurek[Phys.Rev.Lett.88(2001)017901]and the measurement-induced disturbance(MID)method by Luo[Phys.Rev.A 77(2008)022301].It is found that both of them are functions of a parameter partially characterizing the concerned states,however,quantum correlations evaluated via the convenient MID method are somewhat overestimated.

Asymptotical Locking Tomography of High-Dimensional Entanglement

High-dimensional(HD)entanglement provides a very promising way of transcending the limitations of the twodimensional entanglement between qubits for increasing channel capacity in many quantum protocols.In the pursuit of capitalizing on the HD entangled states,one of the central issues is to unambiguously and comprehensively quantilfy and reconstruct them.The full quantum state tomography is a unique solution,but it is undesirable and even impractical because the measurements increase rapidly in d^4 for a bipartite d-dimensional quantum state.Here we present a very efficient and practical tomography method—asymptotical locking tomography(ALT),which can harvest full information of bipartite d-dimensional entangled states by very few measurements less than 2 d^2 only.To showcase the validity and reasonableness of our ALT,we carry out the test with the two-photon spin-orbital angular momentum hyperentangled states in a four-dimensional subspace.Besides high-efficiency and practicality,our ALT is also universal and can be generalized into multipartite HD entanglement and other quantum systems.