检索结果-南通市图书馆

Deviation Inequality for the Number of k-Cycles in a random graph

在线全文

学校读者我要写书评

暂无评论

Wuhan University Journal of Natural Sciences 2009年第1期14卷 11-13页

作者： WANG Yanqing GAO Fuqing School of Mathematics and Statistics Wuhan UniversityWuhan 430072 Hubei China

We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By construct- ing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper.

关键词： random graph deviation inequality k-cycles

A random Geometric graph Coverage Model of Wireless Sensor Networks

在线全文

学校读者我要写书评

暂无评论

A Random Geometric Graph Coverage Model of Wireless Sensor N...

Efficient unequal error protection for online fountain codes

2006 the IET International Conference on Wireless Mobile & Multimedia Networks

作者： Yan Ren Yajuan Qin Bo Wang Hongke Zhang Sidong Zhang School of Electronics and Information Engineering Beijing Jiaotong University Beijing 100044 P. R. China

＜正＞A new random geometric graph coverage model is presented in this article. Compared with other old simple models, this new model considers not only the sensitivity of node but also the reliability of links. It is more appropriate to real situations, affected by various factors. The model shows its applicability when all wireless sensor networks’ （WSN） nodes obtaining its own coordinate for coverage and surveillance purposes. We also analyze some key parameters of WSN as a new model of random geometric graph and propose a simple greedy localization algorithm. In the end, empirical results demonstrate the validity of proposed model and algorithm.

关键词： wireless sensor networks random graph coverage greedy algorithm

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Journal of Systems Engineering and Electronics 2024年第2期35卷 286-293页

作者： SHI Pengcheng WANG Zhenyong LI Dezhi LYU Haibo School of Electronics and Information Engineering Harbin Institute of TechnologyHarbin 150001China Shenzhen Academy of Aerospace Technology Shenzhen 518057China

In this paper,an efficient unequal error protection(UEP)scheme for online fountain codes is *** the buildup phase,the traversing-selection strategy is proposed to select the most important symbols(MIS).Then,in the completion phase,the weighted-selection strategy is applied to provide low *** performance of the proposed scheme is analyzed and compared with the existing UEP online fountain *** results show that in terms of MIS and the least important symbols(LIS),when the bit error ratio is 10-4,the proposed scheme can achieve 85%and 31.58%overhead reduction,respectively.

关键词： online fountain code random graph unequal error protection(UEP) rateless code

Convergence of Distributed Gradient-Tracking-Based Optimization Algorithms with random graphs

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2021年第4期34卷 1438-1453页

作者： WANG Jiexiang FU Keli GU Yu LI Tao School of Mechatronic Engineering and Automation Shanghai UniversityShanghai 200444China Key Laboratory of Pure Mathematics and Mathematical Practice School of Mathematical SciencesEast China Normal UniversityShanghai 200241China

This paper studies distributed convex optimization over a multi-agent system,where each agent owns only a local cost function with convexity and Lipschitz continuous *** goal of the agents is to cooperatively minimize a sum of the local cost *** underlying communication networks are modelled by a sequence of random and balanced digraphs,which are not required to be spatially or temporally independent and have any special *** authors use a distributed gradient-tracking-based optimization algorithm to solve the optimization *** the algorithm,each agent makes an estimate of the optimal solution and an estimate of the average of all the local *** values of the estimates are updated based on a combination of a consensus method and a gradient tracking *** authors prove that the algorithm can achieve convergence to the optimal solution at a geometric rate if the conditional graphs are uniformly strongly connected,the global cost function is strongly convex and the step-sizes don’t exceed some upper bounds.

关键词： Distributed optimization geometric convergence gradient tracking random graph

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND random graphS

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Scientia 2011年第2期31卷 634-640页

作者： M.I. Ostrovskii Department of Mathematics and Computer Science St. John's University

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

关键词： Bipartite graph random graph minimum congestion spanning tree

A Note on the Existence of Fractional f-factors in random graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2014年第3期30卷 677-680页

作者： Jian-sheng CAI Xiao-yang WANG Gui-ying YAN School of Mathematics and Information Science Weifang University Beijing Anzhen Hospital Capital Medical University Academy of Mathematics and System Science Chinese Academy of Science

Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.

关键词： random graph probabilistic method f-factor fractional f-factor

Toward the minimum vertex cover of complex networks using distributed potential games

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2023年第1期66卷 244-263页

作者： Jie CHEN Xiang LI Adaptive Networks and Control Lab Department of Electronic Engineering Fudan University Institute of Complex Networks and Intelligent Systems Shanghai Research Institute for Intelligent Autonomous SystemsTongji University

Vertex cover of complex networks is essentially a major combinatorial optimization problem in network science, which has wide application potentials in engineering. To optimally cover the vertices of complex networks, this paper employs a potential game for the vertex cover problem, designs a novel cost function for network vertices, and proves that the solutions to the minimum value of the potential function are the minimum vertex covering(MVC) states of a general complex network. To achieve the optimal(minimum) covering states, we propose a novel distributed time-variant binary log-linear learning algorithm,and prove that the MVC state of a general complex network is attained under the proposed optimization algorithm. Furthermore, we estimate the upper bound of the convergence rate of the proposed algorithm,and show its effectiveness and superiority using numerical examples with representative complex networks and optimization algorithms.

关键词： minimum vertex cover Nash equilibrium convergence rate scale-free network random graph

Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Physics,Mechanics & Astronomy) 2022年第3期65卷 33-38页

作者： Hai-Jun Zhou CAS Key Laboratory for Theoretical Physics Institute of Theoretical PhysicsChinese Academy of SciencesBeijing 100190China MinJiang Innovative Center for Theoretical Physics MinJiang UniversityFuzhou 350108China School of Physical Sciences University of Chinese Academy of SciencesBeijing 100049China

The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack(CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erd?s-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.

关键词： K-core collapse spin glass model tree packing optimal initial condition random graph

Joint probability generating function for degrees of active/passive random intersection graphs

在线全文

学校读者我要写书评

暂无评论

Frontiers of Mathematics in China 2012年第1期7卷 117-124页

作者： Yilun SHANG Institute for Cyber Security University of Texas at San AntonioSan AntonioTX 78249USA

Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of GactVe（n, re, p） and GPaSSiW（n, re, p）, which are genera... 详细信息

关键词： random graph intersection graph degree generating function