Print Email Facebook Twitter Random line graphs and a linear law for assortativity Title Random line graphs and a linear law for assortativity Author Liu, D. Trajanovski, S. Van Mieghem, P. Faculty Electrical Engineering, Mathematics and Computer Science Date 2013-01-31 Abstract For a fixed number N of nodes, the number of links L in the line graph H(N,L) can only appear in consecutive intervals, called a band of L. We prove that some consecutive integers can never represent the number of links L in H(N,L), and they are called a bandgap of L. We give the exact expressions of bands and bandgaps of L. We propose a model which can randomly generate simple graphs which are line graphs of other simple graphs. The essence of our model is to merge step by step a pair of nodes in cliques, which we use to construct line graphs. Obeying necessary rules to ensure that the resulting graphs are line graphs, two nodes to be merged are randomly chosen at each step. If the cliques are all of the same size, the assortativity of the line graphs in each step are close to 0, and the assortativity of the corresponding root graphs increases linearly from ?1 to 0 with the steps of the nodal merging process. If we dope the constructing elements of the line graphs—the cliques of the same size—with a relatively smaller number of cliques of different size, the characteristics of the assortativity of the line graphs is completely altered. We also generate line graphs with the cliques whose sizes follow a binomial distribution. The corresponding root graphs, with binomial degree distributions, zero assortativity, and semicircle eigenvalue distributions, are equivalent to Erd?s-Rényi random graphs. To reference this document use: http://resolver.tudelft.nl/uuid:fb00d912-6de2-401a-abe7-0bb3a90aaf30 DOI https://doi.org/10.1103/PhysRevE.87.012816 Publisher American Physical Society ISSN 1539-3755 Source http://link.aps.org/doi/10.1103/PhysRevE.87.012816 Source Physical Review E, 87 (1), 2013 Part of collection Institutional Repository Document type journal article Rights © 2013 American Physical Society Files PDF Liu_2013.pdf 802.5 KB Close viewer /islandora/object/uuid:fb00d912-6de2-401a-abe7-0bb3a90aaf30/datastream/OBJ/view