- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Fall 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Monday, October 30, 2023 - 15:45 to 16:45
Gates 114 and streaming (via Zoom)
Host:
Eshan Chattopadhyay
Categories:
Degree Distribution Identifiability of Stochastic Kronecker Graphs
Abstract: Network generation for realistic, real-world processes is an important problem in the biological, social, and physical sciences. Large-scale analysis of the distributions of the networks graphs observed in naturally-occurring phenomena has revealed that the degrees of such graphs follow a power-law or lognormal distribution. Many network or graph generation algorithms rely on the Kronecker multiplication primitive. Seshadhri, Pinar, and Kolda (J. ACM, 2013) proved that Stochastic Kronecker Graph (SKG) models cannot generate graph with degree distribution that follows a power-law or lognormal distribution. As a result, variants of the SKG model have been proposed to generate graphs which approximately follow degree distributions, without any significant oscillations. However, all existing solutions either require significant additional parameterization or have no provable guarantees on the degree distribution.
In this work, we present statistical and computational identifiability notions which imply separation of SKG models. We prove that SKG models in different identifiability classes can be separated by the existence of isolated vertices and connected components. In addition, we present and analyze an efficient algorithm that can get rid of oscillations in the degree distribution by mixing Kronecker seeds of relative prime dimensions.
Based on joint work with Dimitris Kalimeris.
Bio: Daniel G. Alabi is a Junior Fellow of the Simons Foundation Society of Fellows and postdoctoral researcher hosted by Prof. Daniel Hsu at Columbia University. He earned his Ph.D. in computer science from Harvard University, where he was advised by Prof. Salil Vadhan. Also, he is the president and co-founder of NaijaCoder, Inc. NaijaCoder aims to proliferate early computer science education and research in Nigeria, and Africa in general. His research interests lie primarily in the design and analysis of algorithms with a focus on privacy-preserving applications. Some of the awards he earned during his Ph.D. include: a Ph.D. Fellowship from Meta AI, a Courtlandt Memorial Fellowship from Harvard GSAS, and a Harvard Certificate of Distinction in Teaching.