اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدModel-free consistency of graph partitioning
59
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we exploit the theory of dense graph limits to provide a new framework to study the stability of graph partitioning methods, which we call structural consistency. Both stability under perturbation as well as asymptotic consistency (i.e., convergence with probability $1$ as the sample size goes to infinity under a fixed probability model) follow from our notion of structural consistency. By formulating structural consistency as a continuity result on the graphon space, we obtain robust results that are completely independent of the data generating mechanism. In particular, our results apply in settings where observations are not independent, thereby significantly generalizing the common probabilistic approach where data are assumed to be i.i.d. In order to make precise the notion of structural consistency of graph partitioning, we begin by extending the theory of graph limits to include vertex colored graphons. We then define continuous node-level statistics and prove that graph partitioning based on such statistics is consistent. Finally, we derive the structural consistency of commonly used clustering algorithms in a general model-free setting. These include clustering based on local graph statistics such as homomorphism densities, as well as the popular spectral clustering using the normalized Laplacian. We posit that proving the continuity of clustering algorithms in the graph limit topology can stand on its own as a more robust form of model-free consistency. We also believe that the mathematical framework developed in this paper goes beyond the study of clustering algorithms, and will guide the development of similar model-free frameworks to analyze other procedures in the broader mathematical sciences.
قيم البحث
اقرأ أيضاً
We review the theory of Cheeger constants for graphs and quantum graphs and their present and envisaged applications.
The quadrilateral graph Q(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 3, whereas the pentagonal graph W(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 4. In this
paper, closed-form formulas of resistance distance and Kirchhoff index for quadrilateral graph and pentagonal graph are obtained whenever G is an arbitrary graph.
A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In
this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $Gamma=(V,E)$, ($psi_{k}^{gd}(Gamma)$) $psi_k^{d}(Gamma)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $psi_k^{d}(Gamma)$ and $psi_{k}^{gd}(Gamma)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Gamma_1times Gamma_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $Gamma_i$ into (global) defensive $k_i$-alliances, $iin {1,2}$.
We show that for $n geq 3, n e 5$, in any partition of $mathcal{P}(n)$, the set of all subsets of $[n]={1,2,dots,n}$, into $2^{n-2}-1$ parts, some part must contain a triangle --- three different subsets $A,B,Csubseteq [n]$ such that $Acap B$, $Acap
C$, and $Bcap C$ have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into $2^{n-2}$ triangle-free parts. We also address a more general Ramsey-type problem: for a given graph $G$, find (estimate) $f(n,G)$, the smallest number of colors needed for a coloring of $mathcal{P}(n)$, such that no color class contains a Berge-$G$ subhypergraph. We give an upper bound for $f(n,G)$ for any connected graph $G$ which is asymptotically sharp (for fixed $k$) when $G=C_k, P_k, S_k$, a cycle, path, or star with $k$ edges. Additional bounds are given for $G=C_4$ and $G=S_3$.
The fractional matching number of a graph G, is the maximum size of a fractional matching of G. The following sharp lower bounds for a graph G of order n are proved, and all extremal graphs are characterized in this paper. (1)The sum of the fractiona
l matching number of a graph G and the fractional matching number of its complement is not less than n/2 , where n is not less than 2. (2) If G and its complement are non-empty, then the sum of the fractional matching number of a graph G and the fractional matching number of its complement is not less than (n+1)/2, where n is not less than 28. (3) If G and its complement have no isolated vertices, then the sum of the fractional matching number of a graph G and the fractional matching number of its complement is not less than (n+4)/2, where n is not less than 28.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
