It is essential for CS students to graduate with competence about ethics and societal impacts of technology. We designed and taught a new reading discussion course, at Grinnell College, Algorithms, Ethics, and Society, for advanced undergraduate students who have completed CS1 and CS2. Course topics included Identity in Computing, Tech Ethics, Algorithms Informing Policies, Large Language Models, Networks and Social Media, Health Applications, and Robotics. We encountered some challenges with the discussion format, which we addressed by upholding class norms, employing discussion techniques learned from humanities and social science colleagues, and being open to learn from our mistakes.

We present a straightforward paradigm for designing simple, efficient generators for a wide variety of hypergraph models. This approach yields asymptotically optimal algorithms and concise implementations that outperform existing implementations by multiple orders of magnitude. Our generalization of ball dropping, called functional ball dropping, allows us to generate models that have not been previously treated by ball dropping. We identify natural building blocks of a given hypergraph model (e.g an edge) that can be concatenated to form a sensible representation of hypergraph (e.g. a list of edges). Next, we design a sampler subject to two constraints: the sampler’s resulting distribution of hypergraphs must match the model we generate, and the runtime of the sampler must be proportional to the size of the component it samples. Our algorithm incrementally generates the graph by repeated execution of the sampling function. In this paper, we present a general description of the functional ball dropping approach before applying it to several nontrivial graph models. We present arguments for correctness and complexity of each treatment. Following theoretical analysis, we perform empirical comparative runtime analysis that demonstrates the scalability of our implementations.

In this manuscript we present the HyperKron Graph model: an extension of the Kronecker Model, but with a distribution over hyperedges. We prove that we can efficiently generate graphs from this model in time proportional to the number of edges times a small log-factor, and find that in practice the runtime is linear with respect to the number of edges. We illustrate a number of useful features of the HyperKron model including non-trivial clustering and highly skewed degree distributions. Finally, we fit the HyperKron model to real-world networks, and demonstrate the model's flexibility with a complex application of the HyperKron model to networks with coherent feed-forward loops.

By studying a large number of real world graphs, we find empirical evidence that most real world graphs have a statistically significant power-law distribution with a cutoff in the singular values of the adjacency matrix and eigenvalues of the Laplacian matrix in addition to the commonly conjectured power-law in the degrees. Among these results, power-laws in the singular values appear more consistently than in the degree distribution. The exponents of the power-law distributions are much larger than previously observed. We find a surprising direct relationship between the power-law in the degree distribution and the power-law in the eigenvalues of the Laplacian that was theorized in simple models but is extremely accurate in practice. We investigate these findings in large networks by studying the cutoff value itself, which shows a scaling law for the number of elements involved in these power-laws. Using the scaling law enables us to compute only a subset of eigenvalues of large networks, up to tens of millions of vertices and billions of edges, where we find that those too show evidence of statistically significant power-laws.