|◉||A generative graph model for electrical infrastructure networks |
with E. Purvine, M. Halappanavar, E. Cotilla-Sanchez, in preparation.
|Graph-theoretic modeling of electrical transmission networks is an important area of research with potential applications in areas such as resiliency, vulnerability analysis, and the study of cascading failures. We analyze power grid graph data to discern key characteristics of these networks and use these observations to build a generative graph model capable of capturing these features. We demonstrate the effectiveness of our model by testing it on several real-world datasets and comparing its performance to that of previously known models.|
|◉||Measuring and modeling bipartite graphs with community structure |
S. Aksoy, T.G. Kolda and A. Pinar, to appear in Journal of Complex Networks.
|We propose two generative models for bipartite graphs that can be easily tuned to reproduce the characteristics of real-world networks. The measurements we consider are the degree distributions and the bipartite clustering coefficient, which we refer to as the metamorphosis coefficient. We define edge, node, and degreewise metamorphosis coefficients, enabling a more detailed understanding of the bipartite community structure. Our proposed bipartite Chung-Lu model is able to reproduce real-world degree distributions, and our proposed bipartite "BTER" model reproduces both the degree distributions as well as the degreewise metamorphosis coefficients.|
|◉||Extreme values of the stationary distribution of random walks on directed graphs |
S. Aksoy, F. Chung and X. Peng, Advances in Applied Mathematics, Vol. 81 (2016), pp. 128-155
|The principal ratio of a directed graph is the ratio of maximum to minimum values of vertices in the stationary distribution of a random walk on the graph. In addition to playing a role in bounding the rate of convergence of a random walk, the principal ratio is also regarded as a metric for graph irregularity. We prove an upper bound for this ratio over all strongly connected graphs on $n$ vertices, characterize all graphs achieving the upper bound, and give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded.|
|◉||Graphs with many strong orientations |
S. Aksoy and P. Horn, SIAM Journal on Discrete Math, Vol. 30(2), (2016), pp. 1269-1282
|A strong orientation of an undirected graph is an assignment of directions to is edges yielding a strongly connected directed graph. While determining the existence of a strong orientation is straightforward, it is more difficult to count all strong orientations of a given graph. We establish mild conditions under which almost all of a graphs orientations are strongly connected. We also provide a construction to show these conditions are, up to a small factor, best possible.|
|◉||Coalitions and Cliques in the School Choice Problem |
S. Aksoy, A. Azzam, C. Coppersmith, J. Glass, G. Karaali, X. Zhao, and X. Zhu, Involve, Vol. 8(5), (2015), pp. 801-823
|The school choice mechanism design problem focuses on assignment mechanisms matching students to public schools in a given school district. This note introduces two adjustments to the well-known Gale Shapley Student Optimal Stable Matching Mechanism that address its inefficiency issues. In one we create possibly artificial coalitions among students where some students modify their preference profiles in order to improve the outcome for some other students. Our second approach involves trading cliques among students where those involved improve their assignments by waiving some of their priorities.|
|◉||Bikei, Involutary Biracks, and unoriented link invariants |
S. Aksoy and S. Nelson Journal of Knot Theory and Its Ramifications, Vol. 21(6), (2012), 13 pp.
|We identify a subcategory of biracks which define counting invariants of unoriented links, which we call involutory biracks. In particular, involutory biracks of birack rank $N = 1$ are biquandles, which we call bikei. We define counting invariants of unoriented classical and virtual links using finite involutory biracks, and we give an example of a non-involutory birack whose counting invariant detects the non-invertibility of a virtual knot.|
|◉||School Choice as a One-Sided Matching Problem: Cardinal Utilities and Optimization |
S. Aksoy, A. Azzam, C. Coppersmith, J. Glass, G. Karaali, X. Zhao, and X. Zhu Proceedings of the 2012 International Symposium on Artificial Intelligence and Mathematics, Vol. (2012)
[arXiv] [Conference Proceedings Version]
|We analyze a class of one-sided, cardinal utility maximizing matching mechanisms focused exclusively on student preferences. We adapt a well-known combinatorial optimization technique, the Hungarian algorithm, as the kernel of this class of matching mechanisms. We find that, while such mechanisms can be adapted to meet desirable criteria not met by any previously employed mechanism in the school choice literature, they are not strategyproof.|