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

Limiting empirical spectral distribution for the non-backtracking matrix of an Erdos-Renyi random graph

COMBINATORICS PROBABILITY & COMPUTING 2023年第6期32卷 956-973页

作者： Wang, Ke Wood, Philip Matchett Hong Kong Univ Sci & Technol Dept Math Kowloon Hong Kong Peoples R China Harvard Univ Dept Math Cambridge MA 02138 USA

In this note, we give a precise description of the limiting empirical spectral distribution for the non-backtracking matrices for an Erdos-Renyi graph G(n, p) assuming np / log n tends to infinity. We show that derandomizing part of the non-backtracking random matrix simplifies the spectrum considerably, and then, we use Tao and Vu's replacement principle and the Bauer-Fike theorem to show that the partly derandomized spectrum is, in fact, very close to the original spectrum.

关键词： Random graph non-backtracking matrix eigenvalues

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithm Based on non-backtracking matrix for Community Detection in Signed Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第4期9卷 2200-2211页

作者： Zhong, Zhaoyue Wang, Xiangrong Qu, Cunquan Wang, Guanghui Shandong Univ Sch Math Jinan 250100 Peoples R China Southern Univ Sci & Technol Inst Future Networks Shenzhen 518055 Peoples R China Peng Cheng Lab Res Ctr Networks & Commun Shenzhen 518066 Peoples R China Shandong Univ Data Sci Inst Jinan 250100 Peoples R China

Community detection or clustering is a crucial task for understanding the structure of complex systems. In some networks, nodes are permitted to be linked by either "positive" or "negative" edges;such networks are called signed networks. Discovering communities in signed networks is more challenging than that in unsigned networks. In this study, we innovatively develop a non-backtracking matrix of signed networks, theoretically derive a detectability threshold for this matrix, and demonstrate the feasibility of using the matrix for community detection. We further improve the developed matrix by considering the balanced paths in the network (referred to as a balanced non-backtracking matrix). Simulation results demonstrate that the algorithm based on the balanced non-backtracking matrix significantly outperforms those based on the adjacency matrix, the signed non-backtracking matrix, and other benchmark algorithms. The proposed (improved) matrix shows great potential for detecting communities with or without overlap.

关键词： Image edge detection Mathematical models backtracking Social networking (online) Stochastic processes Proteins Heuristic algorithms Community detection detectability threshold non-backtracking matrix signed networks spectral analysis

来源：评论

学校读者我要写书评

暂无评论

Minimizing Spectral Radius of non-backtracking matrix by Edge Removal 21

Minimizing Spectral Radius of Non-Backtracking Matrix by Edg...

引用

30th ACM International Conference on Information and Knowledge Management (CIKM)

作者： Zhang, Zuobai Zhang, Zhongzhi Chen, Guanrong Fudan Univ Shanghai Peoples R China City Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450384469

The spectral radius of the non-backtracking matrix for an undirected graph plays an important role in various dynamic processes running on the graph. For example, its reciprocal provides an excellent approximation of epidemic and edge percolation thresholds. In this paper, we study the problem of minimizing the spectral radius of the non-backtracking matrix of a graph with n nodes and m edges, by deleting k selected edges. We show that the objective function of this combinatorial optimization problem is not submodular, although it is monotone. Since any straightforward approach to solving the optimization problem is computationally infeasible, we present an effective, scalable approximation algorithm with complexity O(n + km). Extensive experiment results for a large set of real-world networks verify the effectiveness and efficiency of our algorithm, and demonstrate that our algorithm outperforms several baseline schemes.

关键词： non-backtracking matrix epidemic threshold spectral radius edge removal graph centrality

来源：评论

学校读者我要写书评

暂无评论

Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix

引用

IMA JOURNAL OF APPLIED MATHEMATICS 2020年第2期85卷 214-230页

作者： Masuda, Naoki Preciado, Victor M. Ogura, Masaki Univ Bristol Dept Engn Math Woodland Rd Bristol BS8 1UB Avon England Univ Buffalo State Univ New York Dept Math Buffalo NY 14260 USA Univ Buffalo State Univ New York Computat & Data Enabled Sci & Engn Program Buffalo NY 14260 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Univ Penn Appl Math & Computat Sci Philadelphia PA 19104 USA Nara Inst Sci & Technol Div Informat Sci Ikoma Nara 6300192 Japan Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

We study the stochastic susceptible-infected-susceptible model of epidemic processes on finite directed and weighted networks with arbitrary structure. We present a new lower bound on the exponential rate at which the probabilities of nodes being infected decay over time. This bound is directly related to the leading eigenvalue of a matrix that depends on the non-backtracking and incidence matrices of the network. The dimension of this matrix is N + M, where N and M are the number of nodes and edges, respectively. We show that this new lower bound improves on an existing bound corresponding to the so-called quenched mean-field theory. Although the bound obtained from a recently developed second-order moment-closure technique requires the computation of the leading eigenvalue of an N-2 x N-2 matrix, we illustrate in our numerical simulations that the new bound is tighter, while being computationally less expensive for sparse networks. We also present the expression for the corresponding epidemic threshold in terms of the adjacency matrix of the line graph and the non-backtracking matrix of the given network.

关键词： networks epidemic processes stochastic processes non-backtracking matrix epidemic threshold

来源：评论

学校读者我要写书评

暂无评论

Targeted influence maximization in complex networks

引用

PHYSICA D-nonLINEAR PHENOMENA 2023年第1期446卷

作者： Zhang, Renquan Wang, Xiaolin Pei, Sen Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China Columbia Univ Mailman Sch Publ Hlth Dept Environm Hlth Sci New York NY 10032 USA

Many real-world applications based on spreading processes in complex networks aim to deliver information to specific target nodes. However, it remains challenging to optimally select a set of spreaders to initiate the spreading process. In this paper, we study the targeted influence maxi-mization problem using a susceptible-infected-recovered (SIR) model as an example. Formulated as a combinatorial optimization, the objective is to identify a given number of spreaders that can maximize the influence over target nodes while minimize the influence over non-target nodes. To find a practical solution to this optimization problem, we develop a theoretical framework based on a message passing process and perform a stability analysis on the equilibrium solution using non -backtracking (NB) matrices. Based on the optimal perturbation on the equilibrium solution, we further introduce a metric, termed targeted collective influence, for each node to identify influential spreaders for targeted spreading processes. The proposed method, validated in both synthetic and real-world networks, outperforms other competing heuristic approaches. Our results provide a framework for analyzing the targeted influence maximization problem and a practical method to identify spreaders in real-world applications.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Influential spreaders Targeted influence maximization Spreading dynamics Targeted spreading non-backtracking matrix Optimal perturbation

来源：评论

学校读者我要写书评

暂无评论

Spectral theory of the non-backtracking Laplacian for graphs

引用

DISCRETE MATHEMATICS 2023年第10期346卷

作者： Jost, Juergen Mulas, Raffaella Torres, Leo Max Planck Inst Math Sci Leipzig Germany Santa Fe Inst Sci Complex Santa Fe NM USA Vrije Univ Amsterdam Amsterdam Netherlands

We introduce a non-backtracking Laplace operator for graphs and we investigate its spectral properties. With the use of both theoretical and computational techniques, we show that the spectrum of this operator captures several structural properties of the graph in a more precise way than the classical operators that have been studied so far in the literature, including the non-backtracking matrix. & COPY;2023 Elsevier B.V. All rights reserved.

关键词： non-backtracking random walks Spectral graph theory non-backtracking matrix Laplacian eigenvalues

来源：评论

学校读者我要写书评

暂无评论

non-backtracking spectra of weighted inhomogeneous random graphs

引用

Mathematical Statistics and Learning 2022年第3-4期5卷 201-271页

作者： Stephan, Ludovic Massoulié, Laurent Information Learning and Physics (IdePHICS) lab École Polytechnique Fédérale de Lausanne (EPFL) Lausanne 1015 Switzerland Inria Paris – Département d’informatique de l’ENS PSL Research University Paris 75012 France

We study a model of random graphs where each edge is drawn independently (but not necessarily identically distributed) from the others, and then assigned a random weight. When the mean degree of such a graph is low, it is known that the spectrum of the adjacency matrix A deviates significantly from that of its expected value EA. In contrast, we show that over a wide range of parameters the top eigenvalues of the non-backtracking matrix B – a matrix whose powers count the non-backtracking walks between two edges – are close to those of EA, and all other eigenvalues are confined in a bulk with known radius. We also obtain a precise characterization of the scalar product between the eigenvectors of B and their deterministic counterparts derived from the model parameters. This result has many applications, in domains ranging from (noisy) matrix completion to community detection, as well as matrix perturbation theory. In particular, we establish as a corollary that a result known as the Baik–Ben Arous–Péché phase transition, previously established only for rotationally invariant random matrices, holds more generally for matrices A as above under a mild concentration hypothesis. © 2022 European Mathematical Society.

关键词： community detection non-backtracking matrix Random graphs

来源：评论

学校读者我要写书评

暂无评论

Detecting the number of clusters in a network

引用

JOURNAL OF COMPLEX NETWORKS 2020年第6期8卷

作者： Budel, Gabriel Van Mieghem, Piet Delft Univ Technol Fac Elect Engn Math & Comp Sci Delft Netherlands

Many clustering algorithms for complex networks depend on the choice for the number of clusters and it is often unclear how to make this choice. The number of eigenvalues located outside a circle in the spectrum of the non-backtracking matrix was conjectured to be an estimator of the number of clusters in a graph. We compare the estimate of the number of clusters obtained from the spectrum of the non-backtracking matrix with three estimators based on the concept of modularity and evaluate the methods on several benchmark graphs. We find that the non-backtracking method detects the number of clusters better than the modularity-based methods for the graphs in our simulation study, especially when the clusters have slightly different sizes. The estimates of the non-backtracking method are narrowly distributed around the true number of clusters for all benchmark graphs considered. Additionally, for graphs without a clustering structure, the non-backtracking method detects exactly one cluster, which is a convenient property of an estimator of the number of clusters. However, the lack of a well-defined concept of a cluster prevents sharp conclusions.

关键词： Complex Networks Community Detection Spectral Clustering Number of Clusters non-backtracking matrix

来源：评论

学校读者我要写书评

暂无评论

backtracking activation impacts the criticality of excitable networks

引用

NEW JOURNAL OF PHYSICS 2020年第1期22卷 1-1页

作者： Zhang, Renquan Quan, Guoyi Wang, Jiannan Pei, Sen Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China Beihang Univ Res Inst Frontier Sci Beijing 100191 Peoples R China Minist Educ Key Lab Math Informat & Behav Semant Beijing Peoples R China Columbia Univ Mailman Sch Publ Hlth Dept Environm Hlth Sci New York NY 10032 USA

Networks of excitable elements are widely used to model real-world biological and social systems. The dynamic range of an excitable network quantifies the range of stimulus intensities that can be robustly distinguished by the network response, and is maximized at the critical state. In this study, we examine the impacts of backtracking activation on system criticality in excitable networks consisting of both excitatory and inhibitory units. We find that, for dynamics with refractory states that prohibit backtracking activation, the critical state occurs when the largest eigenvalue of the weighted non-backtracking (WNB) matrix for excitatory units, lambda(E)(NB), is close to one, regardless of the strength of inhibition. In contrast, for dynamics without refractory state in which backtracking activation is allowed, the strength of inhibition affects the critical condition through suppression of backtracking activation. As inhibitory strength increases, backtracking activation is gradually suppressed. Accordingly, the system shifts continuously along a continuum between two extreme regimes-from one where the criticality is determined by the largest eigenvalue of the weighted adjacency matrix for excitatory units, lambda(E)(W), to the other where the critical state is reached when lambda(E)(NB) is close to one. For systems in between, we find that lambda(E)(NB)<1 and lambda(E)(W)>1 at the critical state. These findings, confirmed by numerical simulations using both random and synthetic neural networks, indicate that backtracking activation impacts the criticality of excitable networks.

关键词： excitable networks criticality backtracking activation non-backtracking matrix excitatory inhibitory networks dynamic range

来源：评论

学校读者我要写书评

暂无评论

Length Spectrum Theory, non-backtracking Cycles, and Two Graph Analysis Tasks 2

Length Spectrum Theory, Non-backtracking Cycles, and Two Gra...

引用

2nd ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) / Workshop on Network Data Analytics (NDA)

作者： Eliassi-Rad, Tina Northeastern Univ Boston MA 02115 USA

ISBN: (纸本)9781450367899

Two basic tasks in graph analysis are: (1) computing the distance between two graphs and (2) embedding of the graph elements (i.e., nodes or links) into a lower-dimensional space. The former task has numerous applications from k-nearest neighbor search, to clustering a collection of graphs, to transfer learning. Unfortunately, there exists no canonical way of computing the distance between two finite graphs because the dissimilarity problem is ill-defined. Despite this fact, the relevant literature contains many methods for measuring graph distance with different heuristics, computational efficiency, interpretability, and theoretical soundness [1]. We introduce a graph distance, called the non-backtracking Spectral Distance (NBD), which is theoretically sound and interpretable. NBD is based on a mathematical construct from algebraic topology (in particular, homotopy) called the length spectrum. The length spectrum of a graph is a function defined on the graph's first homotopy group (a.k.a. the fundamental group);and it uniquely characterizes a graph's 2-core up to isometry [2].1 Thus, if two graphs have the same length spectra, then their 2-cores are isometric. We show the relationship between a graph's length spectrum and its non-backtracking cycles;and present a method based on computing the eigenvalues of a graph's non-backtracking matrix. For the second task (i.e., graph embedding), most existing methods are stochastic and depend on black-box models such as deep networks. Both of these characteristics make their output difficult to analyze. We propose the non-backtracking Embedding Dimensions (NBED) for finding a graph embedding in low-dimensional space by computing the eigenvectors of the non-backtracking matrix. Both NBD and NBED are interpretable in terms of features of complex networks such as hubs, triangles, edge centrality, and communities. We showcase the usefulness of both NBD and NBED in experiments on synthetic and real-world networks. © 2019 Associat

关键词： Graph distance topological data analysis length spectrum non-backtracking matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：