检索结果-内蒙古大学图书馆

AN IMPOSSIBILITY RESULT FOR RECONSTRUCTION IN THE DEGREE-CORRECTED STOCHASTIC BLOCK MODEL

ANNALS OF APPLIED PROBABILITY 2018年第5期28卷 3002-3027页

作者： Gulikers, Lennart Lelarge, Marc Massoulie, Laurent Microsoft Res INRIA Joint Ctr Campus Ecole PolytechBatiment Alan Turing F-91120 Palaiseau France INRIA Paris 2 Rue Simone IffCS 42112 F-75589 Paris 12 France Ecole Normale Super Paris France

We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on n nodes, having i.i.d. weights (phi u)(u)(n)=i (possibly heavytailed), partitioned into q >= 2 asymptotically equal-sized clusters. The model parameters are two constants a, b > 0 and the finite second moment of the weights Phi((2)). Vertices u and v are connected by an edge with probability phi u phi v/na when they are in the same class and with probability phi u phi v/nb otherwise. We prove that it is information-theoretically impossible to estimate the clusters in a way positively correlated with the true community structure when (a - b)(2) (Phi)((2)) <= q (a + b). As by-products of our proof we obtain (1) a precise coupling result for local neighbourhoods in DC-SBMs, that we use in Gulikers, Lelarge and Massoulie (2016) to establish a law of large numbers for local-functionals and (2) that long-range interactions are weak in (power-law) DC-SBMs.

关键词： Social and information networks random graphs degree-corrected stochastic block model spectral algorithm machine learning

来源：评论

学校读者我要写书评

暂无评论

LEARNING SPARSE GRAPHONS AND THE GENERALIZED KESTEN-STIGUM THRESHOLD

引用

ANNALS OF STATISTICS 2023年第2期51卷 599-623页

作者： Abbe, Emmanuel Li, Shuangping Sly, Allan Ecole Polytech Fed Lausanne Inst Math Lausanne Switzerland Princeton Univ PACM Princeton NJ USA Princeton Univ Dept Math Princeton NJ USA

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper pro-vides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-k projec-tion of a graphon in the L2 metric if the top k eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.

关键词： Inference on networks graphon spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

Synthesis of a robust optimal system for stabilizing a plant with failing elements

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2000年第3期36卷 442-449页

作者： Blokhin, LN Kazak, VN Int Univ Civil Aviat Kiev Ukraine

An original performance functional is proposed for problems of synthesis of highly accurate stabilizing systems, which consist of an element that is a measure of the sensitivity of the closed-loop system to arbitrary changes of the controlled plant. A new spectral algorithm is considered for the synthesis of optimal stabilizing systems. An analytical example of the synthesized system is given to illustrate the high efficiency of the synthesis procedure.

关键词： stabilizing system performance functional spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

Clustering High-Dimensional Noisy Categorical Data

引用

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION 2024年第548期119卷 3008-3019页

作者： Tian, Zhiyi Xu, Jiaming Tang, Jen IQVIA Wayne PA USA Duke Univ Fuqua Sch Business Durham NC USA Purdue Univ Daniels Sch Business W Lafayette IN USA

Clustering is a widely used unsupervised learning technique that groups data into homogeneous clusters. However, when dealing with real-world data that contain categorical values, existing algorithms can be computationally costly in high dimensions and can struggle with noisy data that has missing values. Furthermore, except for one algorithm, no others provide theoretical guarantees of clustering accuracy. In this article, we propose a general categorical data encoding method and a computationally efficient spectral-based algorithm to cluster high-dimensional noisy categorical data (nominal or ordinal). Under a statistical model for data on m attributes from n subjects in r clusters with missing probability E, we show that our algorithm exactly recovers the true clusters with high probability when mn(1-epsilon) >= CMr(2) log(3) M, with M = max(n,m) and a fixed constant C. In addition, we show that mn(1-epsilon)(2) >= r delta/2 with 0 < delta < 1 is necessary for any algorithm to succeed with probability at least (1 + delta)/2. In cases where m = n and r are fixed, the sufficient condition matches with the necessary condition up to a polylog(n) factor. In numerical studies our algorithm outperforms several existing algorithms in both clustering accuracy and computational efficiency. Supplementary materials for this article are available online.

关键词： Categorical values Clustering Clustering accuracy High dimensions Noisy and sparse data spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

CONSISTENCY OF spectral HYPERGRAPH PARTITIONING UNDER PLANTED PARTITION MODEL

引用

ANNALS OF STATISTICS 2017年第1期45卷 289-315页

作者： Ghoshdastidar, Debarghya Dukkipati, Ambedkar Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random nonuniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning nonuniform hypergraphs.

关键词： Hypergraph stochastic block model spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

spectral methods for testing membership in certain post classes and the class of forcing functions

引用

IEEE SIGNAL PROCESSING LETTERS 2004年第2期11卷 289-292页

作者： Shmulevich, I Lähdesmäki, H Egiazarian, K Univ Texas MD Anderson Canc Ctr Canc Genom Lab Houston TX 77030 USA Tampere Univ Technol Inst Signal Proc FIN-33720 Tampere Finland

Forcing functions represent an important class of Boolean functions that have been extensively studied in the analysis of the dynamics of random Boolean networks as models of genetic regulatory systems. Several other so-called Post classes of Boolean functions are closely related to forcing functions and have been used in learning theory as well as in control systems. We develop novel spectral algorithms to test membership of a Boolean function in these classes. These algorithms are highly efficient and are essential in learning problems, especially in the context of genetic regulatory networks, where the same learning procedures are applied repeatedly.

关键词： forcing function PoA class spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

SPLITTING LANDAU LEVELS ON THE 2D TORUS BY PERIODIC PERTURBATIONS

引用

INTERNATIONAL JOURNAL OF MODERN PHYSICS C 2008年第11期19卷 1753-1761页

作者： Onofri, E. Univ Montpellier 2 Lab Phys Theor & Astroparticules F-34095 Montpellier 05 France Univ Parma Dept Phys I-43100 Parma Italy Ist Nazl Fis Nucl Grp Collegato Parma I-43100 Parma Italy

We study the spectrum of the Schroedinger operator for a particle constrained on a two-dimensional flat torus under the combined action of a transverse magnetic field and a conservative force. A numerical method is presented which allows to compute the spectrum with high accuracy. The method employs a fast Fourier transform to accurately represent the momentum variables and takes into account the twisted boundary conditions required by the presence of the magnetic field. An accuracy of 12 digits is attained even with coarse grids. Landau levels are reproduced in the case of a uniform magnetic field satisfying Dirac's condition. A new fine structure of levels within the single Landau level is formed when the field has a sinusoidal component with period commensurable to the integer magnetic charge. This fact is interpreted in terms of the peculiar symmetry Z(N) x Z(N) which holds in the unperturbed case.

关键词： Landau levels spectral algorithm periodic perturbations

来源：评论

学校读者我要写书评

暂无评论

Nearly Linear Time algorithm for Mean Hitting Times of Random Walks on a Graph 20

Nearly Linear Time Algorithm for Mean Hitting Times of Rando...

引用

13th Annual ACM International Conference on Web Search and Data Mining (WSDM)

作者： Zhang, Zuobai Xu, Wanyue Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai Peoples R China

ISBN: (纸本)9781450368223

For random walks on a graph, the mean hitting time H-j from a vertex i chosen from the stationary distribution to the target vertex j can be used as a measure of importance for vertex j, while the Kemeny constant K is the mean hitting time from a vertex i to a vertex j selected randomly according to the stationary distribution. Both quantities have found a large variety of applications in different areas. However, their high computational complexity limits their applications, especially for large networks with millions of vertices. In this paper, we first establish a connection between the two quantities, representing K in terms of H-j for all vertices. We then express both quantities in terms of quadratic forms of the pseudoinverse for graph Laplacian, based on which we develop an efficient algorithm that provides an approximation of H-j for all vertices and K in nearly linear time with respect to the edge number, with high probability. Extensive experiment results on real-life and model networks validate both the efficiency and accuracy of the proposed algorithm.

关键词： Random walk hitting time Kemeny constant spectral algorithm complex network node centrality

来源：评论

学校读者我要写书评

暂无评论

Real-time multispectral data collection, processing, downlink and display: Test and demonstration

Real-time multispectral data collection, processing, downlin...

引用

Airborne Intelligence, Surveillance, Reconnaissance (ISR) Systems and Applications

作者： Runnes, Denise Peterman, Scott Powell, Jonathan Leflore, Chad Martin, Addison Schoonmaker, Jon Henderson, Paula Dirbas, Joseph Crowley, Michael Davies, Adam Radiance Technol Inc 775 N Univ Blvd Mobile AL 36608 USA Adv Coherent Technol San Diego CA 92106 USA PAR Govt Syst Corp La Jolla CA 92037 USA

ISBN: (纸本)9780819471376

Radiance Technologies, Inc. has tested and demonstrated real-time collection and on-board processing of Multispectral Imagery (MSI). Further, the test and demonstration consisted of a real-time downlink from the aircraft to the ground station and real-time display of the processed data product. The multispectral imagery was collected with a low-cost, low-profile MSI sensor, MANTIS-3T, from PAR Government Systems. The data product was created from output of a novel spectral algorithm combination that increases the probability of detection and decreases the false alarm rates for specific objects of interest. The display product was a compressed true color image in which the detected objects were delineated with red pixels. A description of the end-to-end solution, issues encountered as well as their resolution, and results will be discussed.

关键词： real-time spectral processing multispectral remote sensing spectral algorithm reconnaissance MANTIS data downlink

来源：评论

学校读者我要写书评

暂无评论

Improved Cheeger's Inequality: Analysis of spectral Partitioning algorithms through Higher Order spectral Gap 13

Improved Cheeger's Inequality: Analysis of Spectral Partitio...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Kwok, Tsz Chiu Lau, Lap Chi Lee, Yin Tat Gharan, Shayan Oveis Trevisan, Luca CUHK Hong Kong Peoples R China Stanford Univ Stanford CA 94305 USA

Let phi(G) be the minimum conductance of an undirected graph G, and let 0 = lambda(1) = 2, phi(G) = O(kappa) lambda(2)/root lambda(kappa) , and this performance guarantee is achieved by the spectral partitioning algor... 详细信息

ISBN: (纸本)9781450320290

Let phi(G) be the minimum conductance of an undirected graph G, and let 0 = lambda(1) <= lambda(2) <= . . . <= lambda(n) <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any kappa >= 2, phi(G) = O(kappa) lambda(2)/root lambda(kappa) , and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any kappa. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if lambda(kappa) is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.

关键词： Graph partitioning spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：