Narrow Results

The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue of a matrix called the graph Laplacian. The focus of this paper is the use graph theory to compute this eigenvector more quickly.

We have recently shown that one can obtain the numbers and sizes of modules of a software system from the eigenvectors of its modularity matrix symmetrized and weighted by an affinity matrix. However such a weighting still demands a suitable definition of an affinity. This paper offers an alternative way to obtain the same results by means of the eigenvectors of a Laplacian matrix, directly obtained from the modularity matrix without the need of weighting. These two formalizations stand in a mutual isomorphism. We call it bipartite isomorphism since it is most straightforwardly shown by deriving the Laplacian from the modularity matrix and vice versa through the intermediate bipartite graph between two separate sets: the structors’ and the functionals’ sets. This isomorphism is also demonstrated through the equation defining the Laplacian in terms of the modularity matrix, or by the direct mapping of the respective matrices’ eigenvectors. Both matrices and the bipartite graph reflect one central idea: modules are connected components with high cohesion. The Laplacian matrix technique, of which the Fiedler vector is of central importance, is illustrated by case studies. An important claim of this paper is that, independently of the modularity matrix- and Laplacian matrix-specific properties, behind these two alternative matrices there is just one unified algebraic theory of software composition — the Linear Software Models — here concerning the application of the matrices’ eigenvectors to software modularity.

Integrating quadratic form of algebraic connectivity and Perron value of bottleneck matrices, we investigate how the algebraic connectivity of a connected weighted graph behaves under shifting components. Generally speaking, when shift components not containing characteristic vertex from less positive (larger negative) valuation vertices to larger positive (less negative) valuation vertices, or reduce weights of some edges, or add some new blocks, its algebraic connectivity is nonincreasing; when shift components along paths from blocks to other block closer to characteristic block (vertex), or increase weights of some edges, or delete some blocks, its algebraic connectivity is non-decreasing. Therefore, algebraic connectivity could be regarded as a measure of central tendency about blocks of a connected weighted graph with characteristic block (vertex) as its center.

The unicyclic graph C_n,g obtained by appending a cycle C_g of length g to a pendent vertex of a path on n - g vertices is the lollipop graph on n vertices. In [Algebraic connectivity of lollipop graphs, Linear Algebra Appl.434 (2011) 2204–2210], Guo et al. proved that a(C_n,g-1) < a(C_n,g) for g ≥ 4, where a(C_n,g) is the algebraic connectivity of C_n,g. In this paper, we present a new approach which is quite different from that of Guo et al. in proving a(C_n,g-1) < a(C_n,g) for g ≥ 4.

Music plays a prominent role in society and companies have even started studying its aspects for commercial purposes. It is only natural to ask what characteristics make certain songs appealing. While much research has been conducted on the mathematical principles of sound, there has been less focus on analyzing the structure of popular songs from a mathematical perspective. One mathematical tool that researchers have used to study musical structure is seriation, ordering. This paper applies several types of seriation algorithms to conduct a mathematical analysis of the structural qualities of several musical pieces. This paper focuses on 10 popular artists and their musical influences. The artists chosen for this research are linked because of the influences they cite, musical genre, and the popularity of their music. Results show that an artist’s songs have a higher quantitatively measured connection with the artists they cite as influences rather than the artists who they never mention as musical influences.