Physical Sciences and Mathematics Commons^™

Measures Of Centrality Based On The Spectrum Of The Laplacian, Scott D. Pauls, Daniel Remondini

Dartmouth Scholarship

We introduce a family of new centralities, the k-spectral centralities. k-Spectral centrality is a measurement of importance with respect to the deformation of the graph Laplacian associated with the graph. Due to this connection, k-spectral centralities have various interpretations in terms of spectrally determined information.

We explore this centrality in the context of several examples. While for sparse unweighted net- works 1-spectral centrality behaves similarly to other standard centralities, for dense weighted net- works they show different properties. In summary, the k-spectral centralities provide a novel and useful measurement of relevance (for single network elements as well as whole subnetworks) …

An Optimal Lower Bound On The Communication Complexity Of Gap-Hamming-Distance, Amit Chakrabarti, Oded Regev

Dartmouth Scholarship

We prove an optimal Ω(n) lower bound on the randomized communication complex- ity of the much-studied gap-hamming-distance problem. As a consequence, we obtain essentially optimal multipass space lower bounds in the data stream model for a number of fundamental prob- lems, including the estimation of frequency moments. The gap-hamming-distance problem is a communication problem, wherein Alice and Bob receive n-bit strings x and y, respectively. They are promised that the Hamming distance between x and y is either at least n/2 + √n or at most n, and their goal is to decide which of these is the case. Since …

Quantitative Patterns Of Stylistic Influence In The Evolution Of Literature, James M. Hughes, Nicholas J. Foti, David C. Krakauer, Daniel N. Rockmore

Dartmouth Scholarship

Literature is a form of expression whose temporal structure, both in content and style, provides a historical record of the evolution of culture. In this work we take on a quantitative analysis of literary style and conduct the first large-scale temporal stylometric study of literature by using the vast holdings in the Project Gutenberg Digital Library corpus. We find temporal stylistic localization among authors through the analysis of the similarity structure in feature vectors derived from content-free word usage, nonhomogeneous decay rates of stylistic influence, and an accelerating rate of decay of influence among modern authors. Within a given time …

Fixed Points And Excedances In Restricted Permutations, Sergi Elizalde

Dartmouth Scholarship

Using an unprecedented technique involving diagonals of non-rational generating functions, we prove that among the permutations of length $n$ with $i$ fixed points and $j$ excedances, the number of 321-avoiding ones equals the number of 132-avoiding ones, for any given $i,j$. Our theorem generalizes a result of Robertson, Saracino and Zeilberger. Even though bijective proofs have later been found by the author jointly with Pak and with Deutsch, this paper contains the original analytic proof that was presented at FPSAC 2003.