ABSTRACT. A variety of network modeling problems begin by generating a degree sequence drawn from a given probability distribution. If the randomly generated sequence is not graphic, we give two new approaches for generating a graphic approximation of the sequence. These schemes are fast and do not require work more than a linear amount of memory, allowing this type of analysis to be performed on very large integer sequences.

ABSTRACT. Community detection is a central topic in network science, where the community structure observed in many real networks is sought through the principled clustering of nodes. Spectral methods give well-established approaches to the problem in the undirected setting; however, they generally do not account for edge directionality. We consider a directed spectral method that utilizes a graph Laplacian defined for non-symmetric adjacency matrices. We give the theoretical motivation behind this directed graph Laplacian, and demonstrate its connection to an objective function that reflects a notion of how communities of nodes in directed networks should behave. Applying the method to directed networks, we compare the results to undirected spectral clustering on symmetrized versions of the adjacency matrices. A simulation study using a directed stochastic block model shows that directed spectral clustering can succeed where the undirected approach fails. And we find interesting and informative differences between the two approaches in the application to Congressional cosponsorship networks.