Página 1 dos resultados de 19 itens digitais encontrados em 0.004 segundos

The construction of the poset of regular execeptional graphs using equitable partitions

Barbedo, Inês; Cardoso, Domingos M.; Rama, Paula
Fonte: Instituto Politécnico de Bragança Publicador: Instituto Politécnico de Bragança
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
56.66%
An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph. It is shown that the set of regular exceptional graphs is partitioned in three layers. A (k,t)-regular set is a subset of the vertices of a graph, inducing a k-regular subgraph such that every vertex not in the subset has t neighbors in it. A new recursive construction of regular exceptional graphs is proposed, where each regular exceptional graph of the first and the second layer is constructed by a (0,2)-regular set extension. In this talk we present an algorithm based on this recursive construction and show that this technique induces a partial order relation on the set of regular exceptional graphs. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs, and we show that each regular exceptional graph has an equitable partition which, by this construction technique, is extended with a new element, the set of the additional vertices. The recursive construction is generalized to the construction of arbitrary families of regular graphs, by extending a regular graph G with another regular graph H such that V(H) is a (k...

Spectral results on graphs with regularity constraints

Cardoso, D.M.; Rama, P.
Fonte: Elsevier Publicador: Elsevier
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
46.78%
Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k1, τ1)-regular set S1 and a (k2, τ2)-regular set S2 such that k1 - τ1 = k2 - τ2 = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, over(π, ̄), induced by π, and the adjacency matrix of the quotient graph L (G) / over(π, ̄) is obtained from the adjacency matrix of G/π. © 2006 Elsevier Inc. All rights reserved.; CEOC; FCT; FEDER

Laplacian eigenvectors and eigenvalues and almost equitable partitions

Cardoso, D.M.; Delorme, C.; Rama, P.
Fonte: Elsevier Publicador: Elsevier
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
46.77%
Relations between Laplacian eigenvectors and eigenvalues and the existence of almost equitable partitions (which are generalizations of equitable partitions) are presented. Furthermore, on the basis of some properties of the adjacency eigenvectors of a graph, a necessary and sufficient condition for the graph to be primitive strongly regular is introduced. © 2006 Elsevier Ltd. All rights reserved.; CEOC; FCT; FEDER

Equitable bipartitions of graphs and related results

Cardoso, D. M.; Rama, P.
Fonte: Springer Verlag Publicador: Springer Verlag
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
36.34%
CEOC; FCT; FEDER

On the eigenvalues of Euclidean distance matrices

Alfakih,A.Y.
Fonte: Sociedade Brasileira de Matemática Aplicada e Computacional Publicador: Sociedade Brasileira de Matemática Aplicada e Computacional
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/01/2008 EN
Relevância na Pesquisa
46.55%
In this paper, the notion of equitable partitions (EP) is used to study the eigenvalues of Euclidean distance matrices (EDMs). In particular, EP is used to obtain the characteristic polynomials of regular EDMs and non-spherical centrally symmetric EDMs. The paper also presents methods for constructing cospectral EDMs and EDMs with exactly three distinct eigenvalues.

Solving hard instances of maximum stable set problem by equitable partitions

LEO, GIANMARIA
Fonte: La Sapienza Universidade de Roma Publicador: La Sapienza Universidade de Roma
Tipo: Tese de Doutorado
EN_US
Relevância na Pesquisa
46.55%

Block transitivity and degree matrices

Soto, José; Fiala, Jirí
Fonte: ACADEMIC PRESS Publicador: ACADEMIC PRESS
Tipo: Artículo de revista
EN
Relevância na Pesquisa
36.34%
We say that a square matrix M of order r is a degree matrix of a given graph G if there is a so-called equitable partition of its vertices into r blocks with the following property: For any i and j it holds that a vertex from the ith block of the partition has exactly m(i,j) neighbors inside the jth block. We ask whether for a given degree matrix M, there exists a graph G such that M is a degree matrix of G, and in addition, for any two edges e, f spanning between the same pair of blocks there exists an automorphism of G that sends e to f. In this work we affirmatively answer the question for all degree matrices and show a way to construct a graph that witnesses this fact. We further explore a case where the automorphism is required to exchange a given pair of edges and show some positive and negative results.

Scalable Positional Analysis for Studying Evolution of Nodes in Networks

Gupte, Pratik Vinay; Ravindran, Balaraman
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.34%
In social network analysis, the fundamental idea behind the notion of position is to discover actors who have similar structural signatures. Positional analysis of social networks involves partitioning the actors into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. Classical approaches to Positional Analysis, such as Regular equivalence and Equitable Partitions, are too strict in grouping actors and often lead to trivial partitioning of actors in real world networks. An Epsilon Equitable Partition (EEP) of a graph, which is similar in spirit to Stochastic Blockmodels, is a useful relaxation to the notion of structural equivalence which results in meaningful partitioning of actors. In this paper we propose and implement a new scalable distributed algorithm based on MapReduce methodology to find EEP of a graph. Empirical studies on random power-law graphs show that our algorithm is highly scalable for sparse graphs, thereby giving us the ability to study positional analysis on very large scale networks. We also present the results of our algorithm on time evolving snapshots of the facebook and flickr social graphs. Results show the importance of positional analysis on large dynamic networks.; Comment: Presented at the workshop on Mining Networks and Graphs: A Big Data Analytic Challenge...

On the Godsil -- Higman necessary condition for equitable partitions of association schemes

Gavrilyuk, Alexander L.; Mogilnykh, Ivan Yu.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/06/2013
Relevância na Pesquisa
46.77%
In the monograph 'Association schemes', C. Godsil derived a necessary condition for equitable partitions of association schemes and noticed that it could be used to show that certain equitable partitions do not exist. In this short note, we show that, in fact, this condition is not stronger than the well-known Lloyd theorem.

Equitable Partitioning Policies for Mobile Robotic Networks

Pavone, Marco; Arsie, Alessandro; Frazzoli, Emilio; Bullo, Francesco
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/03/2009
Relevância na Pesquisa
36.53%
The most widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multi-agent systems, this principle directly leads to equitable partitioning policies in which (i) the workspace is divided into subregions of equal measure, (ii) there is a bijective correspondence between agents and subregions, and (iii) each agent is responsible for service requests originating within its own subregion. In this paper, we design provably correct, spatially-distributed and adaptive policies that allow a team of agents to achieve a convex and equitable partition of a convex workspace, where each subregion has the same measure. We also consider the issue of achieving convex and equitable partitions where subregions have shapes similar to those of regular polygons. Our approach is related to the classic Lloyd algorithm, and exploits the unique features of power diagrams. We discuss possible applications to routing of vehicles in stochastic and dynamic environments. Simulation results are presented and discussed.; Comment: Paper submitted to IEEE Transactions on Automatic Control in December 2008

Perfect state transfer, graph products and equitable partitions

Ge, Yang; Greenberg, Benjamin; Perez, Oscar; Tamon, Christino
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/09/2010
Relevância na Pesquisa
36.55%
We describe new constructions of graphs which exhibit perfect state transfer on continuous-time quantum walks. Our constructions are based on variants of the double cones [BCMS09,ANOPRT10,ANOPRT09] and the Cartesian graph products (which includes the n-cube) [CDDEKL05]. Some of our results include: (1) If $G$ is a graph with perfect state transfer at time $t_{G}$, where $t_{G}\Spec(G) \subseteq \ZZ\pi$, and $H$ is a circulant with odd eigenvalues, their weak product $G \times H$ has perfect state transfer. Also, if $H$ is a regular graph with perfect state transfer at time $t_{H}$ and $G$ is a graph where $t_{H}|V_{H}|\Spec(G) \subseteq 2\ZZ\pi$, their lexicographic product $G[H]$ has perfect state transfer. (2) The double cone $\overline{K}_{2} + G$ on any connected graph $G$, has perfect state transfer if the weights of the cone edges are proportional to the Perron eigenvector of $G$. This generalizes results for double cone on regular graphs studied in [BCMS09,ANOPRT10,ANOPRT09]. (3) For an infinite family $\GG$ of regular graphs, there is a circulant connection so the graph $K_{1}+\GG\circ\GG+K_{1}$ has perfect state transfer. In contrast, no perfect state transfer exists if a complete bipartite connection is used (even in the presence of weights) [ANOPRT09]. We also describe a generalization of the path collapsing argument [CCDFGS03...

Epidemic Outbreaks in Networks with Equitable or Almost-Equitable Partitions

Bonaccorsi, Stefano; Ottaviano, Stefania; Mugnolo, Delio; De Pellegrini, Francesco
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.53%
We study the diffusion of epidemics on networks that are partitioned into local communities. The gross structure of hierarchical networks of this kind can be described by a quotient graph. The rationale of this approach is that individuals infect those belonging to the same community with higher probability than individuals in other communities. In community models the nodal infection probability is thus expected to depend mainly on the interaction of a few, large interconnected clusters. In this work, we describe the epidemic process as a continuous-time individual-based susceptible-infected-susceptible (SIS) model using a first-order mean-field approximation. A key feature of our model is that the spectral radius of this smaller quotient graph (which only captures the macroscopic structure of the community network) is all we need to know in order to decide whether the overall healthy-state defines a globally asymptotically stable or an unstable equilibrium. Indeed, the spectral radius is related to the epidemic threshold of the system. Moreover we prove that, above the threshold, another steady-state exists that can be computed using a lower-dimensional dynamical system associated with the evolution of the process on the quotient graph. Our investigations are based on the graph-theoretical notion of equitable partition and of its recent and rather flexible generalization...

Square Property, Equitable Partitions, and Product-like Graphs

Hellmuth, Marc; Ostermeier, Lydia; Stadler, Peter F.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.55%
Equivalence relations on the edge set of a graph $G$ that satisfy restrictive conditions on chordless squares play a crucial role in the theory of Cartesian graph products and graph bundles. We show here that such relations in a natural way induce equitable partitions on the vertex set of $G$, which in turn give rise to quotient graphs that can have a rich product structure even if $G$ itself is prime.; Comment: 20 pages, 6 figures

alpha-Kuramoto partitions: graph partitions from the frustrated Kuramoto model generalise equitable partitions

Kirkland, Stephen; Severini, Simone
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/06/2013
Relevância na Pesquisa
36.65%
The Kuramoto model describes the collective dynamics of a system of coupled oscillators. An alpha-Kuramoto partition is a graph partition induced by the Kuramoto model, when the oscillators include a phase frustration parameter. We prove that every equitable partition is an alpha-Kuramoto partition, but that the converse does necessarily not hold. We give an exact characterisation of alpha-Kuramoto bipartitions.; Comment: 7 pages, 3 EPS figures

Measuring dependence powerfully and equitably

Reshef, Yakir A.; Reshef, David N.; Finucane, Hilary K.; Sabeti, Pardis C.; Mitzenmacher, Michael M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.34%
For high-dimensional datasets, it is common to evaluate a measure of dependence on every variable pair and retain the highest-scoring pairs for follow-up. If the statistic used systematically assigns higher scores to some relationship types over others, important relationships may be overlooked. This difficulty is avoided if the statistic is equitable [Reshef et al. 2015a], i.e., if, for some measure of noise, it assigns similar scores to equally noisy relationships regardless of relationship type. In this paper, we introduce and characterize a population measure of dependence called MIC*. We show three ways that MIC* can be viewed: as the population value of MIC, a highly equitable statistic from [Reshef et al. 2011], as a canonical "smoothing" of mutual information, and as the supremum of an infinite sequence defined in terms of optimal one-dimensional partitions of the marginals of the joint distribution. Based on this theory, we introduce an efficient algorithm for computing MIC* from the density of a pair of random variables, and we define a new consistent estimator MICe for MIC* that is efficiently computable. (In contrast, there is no known polynomial-time algorithm for computing MIC.) We show through simulations that MICe has better bias-variance properties than MIC...

Perfect colorings of $Z^2$: Nine colors

Krotov, Denis
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/12/2008
Relevância na Pesquisa
26.12%
We list all perfect colorings of $Z^2$ by 9 or less colors. Keywords: perfect colorings, equitable partitions; Comment: 177 pages (large Appendix). !Attention: .ps is 17Mb, .pdf is 1.6Mb, archived source is 40kb

Equitable Decompositions of Graphs

Barrett, Wayne; Echols, Ryan; Francis, Amanda; Sorensen, Derek; Webb, Ben
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/10/2015
Relevância na Pesquisa
36.46%
The automorphisms of a graph can be used to characterize the graph's symmetries. Here we show that if a graph has any kind of symmetry, it is possible to decompose the graph's (weighted) adjacency matrix $A$ into a number of smaller matrices with respect to any one of its automorphisms. The collective eigenvalues of these resulting matrices are the same as the eigenvalues of the original matrix $A$. Because this decomposition has connections to the theory of equitable partitions it is referred to as an $\textit{equitable decomposition}$. This method of decomposition can also be used on any other matrix that can be associated with a graph, so long as the matrix respects the symmetries of the graph. This includes, for instance, Laplacian matrices. Moreover, the techniques used to equitably decompose a graph can be used to bound the number of simple eigenvalues of undirected graphs.

New infinite families of directed strongly regular graphs via equitable partitions

Gyürki, Štefan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/04/2015
Relevância na Pesquisa
46.66%
In this paper we introduce a construction of directed strongly regular graphs from smaller ones using equitable partitions. Each equitable partition of a single DSRG satisfying several conditions leads to an infinite family of directed strongly regular graphs. We construct in this way dozens of infinite families. For order at most 110, we confirm the existence of DSRGs for 30 previously open parameter sets.; Comment: 27 pages

Structure-preserving model reduction of physical network systems by clustering

Monshizadeh, Nima; van der Schaft, Arjan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/03/2014
Relevância na Pesquisa
26.55%
In this paper, we establish a method for model order reduction of a certain class of physical network systems. The proposed method is based on clustering of the vertices of the underlying graph, and yields a reduced order model within the same class. To capture the physical properties of the network, we allow for weights associated to both the edges as well as the vertices of the graph. We extend the notion of almost equitable partitions to this class of graphs. Consequently, an explicit model reduction error expression in the sense of H2-norm is provided for clustering arising from almost equitable partitions. Finally the method is extended to second-order systems.