Ilya Safro

Theatre

Look back in anger

An Ordinary Miracle

Lion and panther

A Marriage Proposal

Musketeer - Network generation tool.
>Link to download -- will be open soon<

Multiscale solvers for the following problems on (un)weighted graphs:

¤	minimum linear arrangement problem
¤	minimum 2-sum problem
¤	minimum bandwidth problem
¤	minimum workbound problem
¤	minimum k-partitioning problem
¤	network compression-friendly reordering

The corresponing paper on the multiscale methods for linear ordering problems can be found here. The algorithms are implemented in C++ using LEDA and Lapack/Lapack++. Please send me an email if you need these implementations.

Potentially hard graphs for k-partitioning solvers
The archive contains artificialy constructed instances (from real world graphs) that can be difficult for graph k-partitioning solvers.
>>Link to the benchmark<<
Paper: I. Safro, P. Sanders, C. Schulz, "Advanced Coarsening Schemes for Graph Partitioning", SEA 2012, Preprint Argonne National Laboratory ANL/MCS-2016-0112, 2012, download

Benchmark for the minimum logarithmic arrangement problem
The archive contains a benchmark with directed and undirected graphs and numerical results for them. The numerical results for this problem are of particular interest because of their importance for the large-scale network compression.
>>Link to the benchmark<<
Paper: I. Safro, B. Temkin, "Multiscale approach for the network compression-friendly ordering", Journal of Discrete Algorithms, Vol. 9, pp. 190-202, 2011

Publications

I. Safro, L. Segel, "Collective stochastic versions of playable games as metaphors for complex biosystems: Team Collect Four", Complexity 8 (2003), 46-55, download
I. Safro, "The minimum linear arrangement problem", M.Sc. Thesis, Weizmann Institute of Science,2002.
I. Safro, D. Ron, A. Brandt, "Graph Minimum Linear Arrangement by Multilevel Weighted Edge Contractions", Journal of Algorithms, vol. 60/1, pp. 24-41, 2006, download
I. Safro, D. Ron, A. Brandt, "A Multilevel Algorithm for the Minimum 2-sum Problem", Journal of Graph Algorithms and Applications, vol. 10/2, 2006, download
L. Klipcan, I. Safro, B. Temkin, M. Safro, "Optimal growth temperature of prokaryotes correlates with class II amino acid composition", FEBS Letters (Federation of European Biochemical Societies), vol. 580/6, pp. 1672-1676, 2006, download
I. Safro, "Multilevel Algorithms for Combinatorial Optimization Problems", Ph.D. Thesis, The Weizmann Institute of Science, 2007, download
I. Safro, D. Ron, A. Brandt, "Multilevel Algorithms for Linear Ordering Problems", ACM Journal of Experimental Algorithmics, vol. 13, pp. 1.4-1.20, 2008, download
C. Chevalier, I. Safro, "Comparison of coarsening schemes for multilevel graph partitioning", Learning and Intelligent Optimization, LNCS 5851, pp. 191-205. Springer, 2009, download
I. Safro, P. Hovland, J. Shin, M. Strout, "Improving random walk performance", in Proceedings of the International Conference on Scientific Computing (CSC), pp. 108-112, 2009, download
E. Boman, U. Catalyurek, C. Chevalier, K. Devine, I. Safro, M. Wolf, "Advances in Parallel Partitioning, Load Balancing, and Matrix Ordering", Journal of Physics: Conference Series, vol. 180, 2009, download
O. Roderick, I. Safro, "Learning Highly-Filtered Data by Nonlinear Spectral Methods", Learning and Intelligent Optimization, Springer LNCS, vol. 6073, pp. 154-168, 2010, download
J. Chen, I. Safro, "Algebraic Distance on Graphs", SIAM Journal on Scientific Computing, Vol. 33, No. 6, pp. 3468-3490, 2011, download
A. Lyons, I. Safro, J. Utke, "Randomized Heuristics for Exploiting Jacobian Scarcity", accepted in Optimization Methods and Software, 2010, download
D. Ron, I. Safro, A. Brandt, "A fast multigrid algorithm for energy minimization under planar density constraints", SIAM Multiscale Modeling and Simulations, Vol. 8, No. 5, pp. 1599-1620, 2010, download
I. Safro, B. Temkin, "Multiscale approach for the network compression-friendly ordering", Journal of Discrete Algorithms, Vol. 9, pp. 190-202, 2011, download
D. Ron, I. Safro, A. Brandt, "Relaxation-based coarsening and multiscale graph organization", SIAM Multiscale Modeling and Simulations, Vol. 9, No. 1, pp. 407-423, 2011, download
J. Chen, I. Safro, "A Measure of the Connection Strengths between Graph Vertices with Applications", International Conference on Computational Science, Procedia CS, vol. 4, pp. 196-205, 2011
N. Goldberg, S. Leyffer, I. Safro, "Optimal Response to Epidemics and Cyber Attacks in Networks", submitted, Preprint ANL/MCS-1992-0112, 2012, download
I. Safro, P. Sanders, C. Schulz, "Advanced Coarsening Schemes for Graph Partitioning", accepted at International Symposium on Experimental Algorithms, Preprint Argonne National Laboratory ANL/MCS-2016-0112, 2012, download

Book chapters

I. Safro, D. Ron, A. Brandt, "Fast Multilevel Algorithms for Linear Ordering Problems", in Computational Optimization: New Research Developments, Nova Science Publishers, ISBN: 978-1-60692-671-0.

ArXiv/Technical Reports

I. Safro, "Discovery of new hypotheses about the relation of biological objects using MEDLINE information", 2000.
I. Safro, "The minimum linear arrangement problem on proper interval graphs", arXiv, cs.DM/0608008, 2002, download.
S. Benditkis, I. Safro, "Generalizations of the Hanoi Towers problem", arXiv, cs.DM/0612070, 1998, download.
O. Roderick, I. Safro, "Polynomial Interpolation for Predicting Decisions and Recovering Missing Data", Preprint ANL/MCS-P1586-0209, Argonne National Laboratory, 2009.

Selected extended abstracts

L. Brodsky, M. Kositsky, A. Leontovich, Y. Kalaidzidis, I. Safro, M. Shtutman, E. Feinstein, "Gene Expression Analysis Tools", Annual Israeli Bioinformatics Symposium, 2002.
I. Safro, D. Ron, A. Brandt, "Multilevel Algorithms for Linear Ordering Problems", SIAM Workshop on Combinatorial Scientific Computing, 2005, download.
A. Lyons, I. Safro, "Randomized Heuristics for Exploiting Jacobian Scarcity", Dagstuhl Seminar on Combinatorial Scientific Computing, 2009, download.
D. Ron, I. Safro, A. Brandt, "Fast Multilevel Solver for Quadratic Optimization under Planar Density Constraints", European Conference on Operational Research, 2009.
I. Safro, "Algebraic Distance and Its Applications to Combinatorial Scientific Computing Problems", SIAM Workshop on Combinatorial Scientific Computing, 2009.
I. Safro, B.Temkin, "Multiscale approach for network compression-friendly ordering", SIAM Workshop on Combinatorial Scientific Computing, 2011.
I. Safro, "Multiscale Algorithms for Analysis and Optimization Problems on Large Networks", Complex Networks, 2012.

I received my Ph.D. degree from The Weizmann Institute of Science under supervision of Achi Brandt and Dorit Ron, in 2008. As of August 2010, I am an Argonne Scholar in the Laboratory for Advanced Numerical Simulations, Mathematics and Computer Science Division, Argonne National Laboratory. Before that I was a CSCAPES Postdoctoral Fellow at ANL.


Research Interests:
¤	Scientific Computing; Multiscale Methods; Computational Science
¤	Graph theory; Algorithms and Applications; Combinatorial Optimization
¤	Machine Learning and Data Mining; Predicting Decisions; Recovering Missing Data; IR
¤	Massive Data Analysis and Optimization Problems, High-performance Computing
¤	Network Analysis and Generation
¤	Complex Systems

My Erdös number is 3, and this is my Ph.D. genealogy tree (courtesy Mathematics Genealogy Project)

Some Recent Professional Activities

¤	Organizer: Minisymposia "Multilevel methods for graphs and hypergraphs" at SIAM CSE11
¤	Program committee member: LION 2011; LION 2012
¤	Reviewer: Journal of Computational Science; SIAM Journal on Scientific Computing; Machine Learning; Optimization Methods and Software; Information Sciences; Journal of Algorithms in Cognition, Informatics and Logic; JST
¤	Grant Proposals Reviewer for LDRD Grants 2011