Czabarka Eva (University of South Carolina): Partition adjacency matrices |
|
|
|
|
Csütörtök, 29. Május 2014, 11:00 - 12:00
|
|
| Abstract. Havel-Hakimi and respectively Ryser showed that the space of graphs and bipartite graphs with a given degree sequence is connected under simple swaps of edges. This operation is useful in an MCMC algorithm that samples the space of graphs with a given degree sequence. Degree sequence alone does not capture the assortativity of the graph, the tendency of nodes to be connected to vertices of similar or different degrees. To overcome this difficulty, the joint degree matrix of a graph was introduced. Partition adjacency matrices (PAMs) are generalizations of joint degree matrices: given a partition $\{P_1,\ldots,P_M\}$ of the vertex set the $M\times M$ partition adjacency matrics $(a_{ij})$ is defined by $a_{ij}=$ the number of edges connecting a vertex in $P_i$ to a vertex in $P_j$. We will show conditions for a matrix to be the partition adjacency matrix of a graph; prove that under certain condition essentially the same swaps connect the space of all graphs with a given PAM, and give examples that show that these conditions are the best possible in some sense. |
|
Hely : Kalmár Intézet, Árpád tér, szemináriumi szoba |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013
Esemény exportálása