Mauricio Soto

About me

I received a Bachelor and an Engineering (in Mathematics) degree in 2002 and 2005 respectively from the Universidad de Chile .

In 2006 I was awarded a fellowship from CONICYT and the French Embassy in Chile for Master 2 and Doctorate.

I am graduated of the Master Parisien de Recherche en Informatique in 2007 and I started my Ph.D. under the supervision of Laurent Viennot and Fabien de Montgolfier within the team of Distributed Algorithmic and Graphs at LIAFA. My thesis work was part of the projet GANG at INRIA.

I obtain my Ph.D. in 2011 from the Université Paris Diderot. I worked in 2011 as teaching assistant (ATER) at the Université Paris Diderot and in 2012 at the Laboratoire d'Informatique Fondamentale d'Orléans as part of the GAMoC team.

From 2013 to 2015 I developed the research project "Topology and Dynamic in communication networks" at the Universidad de Chile founded founded by CONICYT.

Research Interest

algorithm, graph, Internet topology, communication networks, queueing theory, graph hyperbolicity, clustering, modularity.

Publications

Journals

• p-Box: A new graph model. M.S. and Christopher Thraves. Discrete Mathematics & Theoretical Computer Science, Volume 17, Number 1, Pages 169--186, March 2015.
  Abstract Bibtex Pdf Code

  In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.

  @article{DMTCS2508,
  author = {Mauricio Soto and Christopher Thraves Caro},
  title = {p-Box: A new graph model},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  volume = {17},
  number = {1},
  year = {2015},
  keywords = {},
  abstract = {In this document, we study the scope of the following graph model: each vertex is assigned to a box in R^d and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in R. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.}, issn = {1365-8050},
  url = {http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2508}

  Whit this Java code you can create pBOX graps. Based on Graph Panel by Dr.John.B.Matthews.

• Embedding signed graphs in the line. Eduardo G. Pardo, M.S. and Christopher Thraves. Journal of Combinatorial Optimization, Volume 29, Issue 2, pp 451-471, February 2015. Abstract Bibtex Pdf

  Signed graphs are graphs with an assignment of a positive or a negative sign to each edge. These graphs are helpful to represent different types of networks. For instance, they have been used in social networks, where a positive sign in an edge represents friendship between the two endpoints of that edge, while a negative sign represents enmity. Given a signed graph, an important question is how to embed such a graph in a metric space so that in the embedding every vertex is closer to its positive neighbors than to its negative ones. This problem is known as Sitting Arrangement (SA) problem and it was introduced by Kermarrec et al. in \cite{DBLP:conf/mfcs/KermarrecT11}.

  M. Cygan et al. in \cite{mfcsCygan2012} proved that the decision version of SA problem is NP-Complete when the signed graph has to be embedded into the Euclidean line. In this work, we study the minimization version of SA (MinSA) problem in the Euclidean line. We relate MinSA problem to the well known Quadratic Assignment (QA) problem. We establish such a relation by proving that local minimums in MinSA problem are equivalent to local minimums in a particular case of QA problem. In this document, we design two heuristics based on the combinatorial structure of MinSA problem. %one greedy heuristic and a second heuristic that follows grasp techniques. We experimentally compare their performances against heuristics designed for QA problem. This comparison favors the proposed heuristics.

  @article{DBLP:journals/jco/PardoST15, author = {Eduardo G. Pardo and Mauricio Soto and Christopher Thraves},
  title = {Embedding signed graphs in the line - Heuristics to solve MinSA problem},
  journal = {J. Comb. Optim.},
  volume = {29},
  number = {2},
  pages = {451--471},
  year = {2015},
  url = {http://dx.doi.org/10.1007/s10878-013-9604-1},
  doi = {10.1007/s10878-013-9604-1},
  timestamp = {Mon, 12 Jan 2015 11:00:38 +0100},
  biburl = {http://dblp.uni-trier.de/rec/bib/journals/jco/PardoST15},
  bibsource = {dblp computer science bibliography, http://dblp.org} }
• Adversarial Queuing Theory with Setups. M. Kiwi, M. S., C. Thraves. Theoretical Computer Science, Volume 410, Number 8-10, Pages 670--687, March 2009.
  Abstract Bibtex Pdf

  We look at routing and scheduling problems on Kelly type networks where the injection process is under the control of an adversary. The novelty of the model we consider is that the adversary injects requests of distinct types. Resources are subject to switch-over delays or setups when they begin servicing a new request class. In this new setting, we study the behavior of sensible policies as introduced by Dai and Jennings [J. Dai, O. Jennings, Stabilizing queueing networks with setups, Math. Oper. Res. (2004) 891–922].

  We first show that the model is robust in the sense that under some mild conditions universal stability of work conserving packet routing protocols is preserved for natural variants of the underlying model. Also, the model's equivalence to so called token networks is established.

  We adapt to the multi-type request and setup setting, standard arguments for proving stability. Nevertheless, we provide counterexamples that show that for several reasonable adaptations of contention resolution protocols to the multi-type case, stability results do not carry over from the single-type scenario. This motivates us to explore fluid model based arguments that could be used for proving stability for a given network. Specifically we show analogues of results obtained by Gamarnik [D. Gamarnik, Stability of adversarial queues via fluid model, in: Proc. of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 60-70] but in the multi-type request with setups scenario.

  @article{KST09,
  author = {Kiwi, M. and Soto, M. and Thraves, C.},
  title = {Adversarial queuing theory with setups},
  journal = {Theor. Comput. Sci.},
  volume = {410},
  issue = {8-10},
  month = {March},
  year = {2009},
  issn = {0304-3975},
  pages = {670--687},
  numpages = {18},
  url = {http://dl.acm.org/citation.cfm?id=1502808.1502873},
  doi = {10.1016/j.tcs.2008.09.064},
  acmid = {1502873},
  publisher = {Elsevier Science Publishers Ltd.},
  address = {Essex, UK},
  keywords = {Adversarial queueing theory, Routing protocols, Scheduling protocols, Setups}
  }

International Conferences

• Beyond Perfect Phylogeny: Multisample Phylogeny Reconstruction via ILP. Paola Bonizzoni, Gianluca Della Vedova, Simone Ciccolella, and M.S. 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics (BCB 2017). Boston, MA, August 2017 Abstract Bibtex
• Character-Based Phylogeny Construction and Its Application to Tumor Evolution. Gianluca Della Vedova, Murray Patterson, Raffaella Rizzi and M.S. 13th Conference on Computability in Europe (CiE 2017). Yokohama Japan, December 2011. Abstract Bibtex Pdf

  Character-based Phylogeny Construction is a well-known combinatorial problem whose input is a matrix M and we want to compute a phylogeny that is compatible with the actual species encoded by M.

  In this paper we survey some of the known formulations and algorithms for some variants of this problem. Finally, we present the connections between these problems and tumor evolution, and we discuss some of the most important open problems.

  @Inbook{DellaVedova2017, author="Della Vedova, Gianluca and Patterson, Murray and Rizzi, Raffaella and Soto, Mauricio", editor="Kari, Jarkko and Manea, Florin and Petre, Ion", title="Character-Based Phylogeny Construction and Its Application to Tumor Evolution", bookTitle="Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings", year="2017", publisher="Springer International Publishing", address="Cham", pages="3--13", isbn="978-3-319-58741-7", doi="10.1007/978-3-319-58741-7_1", url="http://dx.doi.org/10.1007/978-3-319-58741-7_1" }
• Asymptotic Modularity of Some Graph Classes. Fabien de Montgolfier, M. S. and Laurent Viennot. 22nd International Symposium on Algorithms and Computation (ISAAC 2011). Yokohama Japan, December 2011. Abstract Bibtex Pdf

  Modularity has been introduced as a quality measure for graph partitioning. It has received considerable attention in several disciplines, especially complex systems. In order to better understand this measure from a graph theoretical point of view, we study the modularity of a variety of graph classes.

  We first consider simple graph classes such as tori and hypercubes. We show that these regular graph families have asymptotic modularity 1 (that is the maximum possible). We extend this result to the general class of unit ball graphs of bounded growth metrics. Our most striking result concerns trees with bounded degree which also appear to have asymptotic modularity 1. This last result can be extended to graphs with constant average degree and to some power-law graphs.

  @InProceedings{msv11c,
  author = {de Montgolfier, Fabien AND Soto, Mauricio AND Viennot, Laurent},
  title = {Asymptotic Modularity of some Graph Classes},
  booktitle = {22nd International Symposium on Algorithms and Computation (ISAAC)},
  pages = {1--10},
  year = 2011,
  x-country = {JP},
  address = {Yokohama},
  }
• Treewidth and Hyperbolicity of the Internet. Fabien de Montgolfier, M. S. et Laurent Viennot. 10th IEEE International Symposium on Network Computing and Applications (IEEE NCA11). Cambridge, MA USA. August 2011. Abstract Bibtex Pdf

  We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level.

  On the one hand, the treewidth of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyperbolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the treewidth and hyperbolicity obtained for classical Internet models and compare with the snapshots.

  @InProceedings{msv11b,
  author = {de Montgolfier, Fabien AND Soto, Mauricio AND Viennot, Laurent},
  title = {Treewidth and Hyperbolicity of the Internet},
  booktitle = {10th IEEE International Symposium on Network Computing and Applications (IEEE NCA)},
  pages = {1--8},
  year = {2011},
  x-language = {EN},
  x-international-audience = {YES},
  x-country = {US},
  address = {Boston},
  }

National Conferences

• Modularité asymptotique de quelques classes de graphes. Fabien de Montgolfier, M. S. et Laurent Viennot. 14èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2012). La Grande Motte, Hérault, France, May 2012. Abstract Bibtex Pdf

  De nombreuses disciplines scientifiques font appel au clustering pour l'analyse de leurs réseaux d'interaction. Pami les très nombreux algorithmes existants, toute une famille utilise la modularité de Newman-Girvan comme objectif à maximiser, et cette valeur est devenue un paramètre de graphe standard. Dans cette étude nous prenons à rebours l'approche empirique usuelle et nous posons la question théorique de la modularité de classes de graphes. Nous montrons que des classes très régulières et sans "clusters" naturels (grilles, hypercubes,...) ont une modularité asymptotiquement 1 (le maximum possible), soit bien plus que les valeurs usuelles des données "bien clusterisées". Nous montrons que sous réserve d'une condition sur le degré maximum, les arbres ont aussi modularité asymptotique 1. Résultat qui nous permet de fournir une borne inférieure pour la modularité des graphes connexes peu denses et de certains power-law graphs, qui ont modularité asymptotique au moins 2/(degré moyen), ainsi qu'un algorithme garantissant cette performance.

  @InProceedings{msv12,
  author = {de Montgolfier, Fabien AND Soto, Mauricio AND Viennot, Laurent},
  title = {Modularité asymptotique de quelques classes de graphes},
  booktitle = {14es Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (ALGOTEL)},
  pages = {1--4},
  year = 2012,
  x-language = {FR},
  x-international-audience = {NO},
  x-country = {FR},
  address = {La Grande Motte}
  }
• Clustering de métrique et clustering de graphe. Fabien de Montgolfier, M. S. et Laurent Viennot. 13es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2011). Cap Estérel, France, March 2011. Abstract Bibtex Pdf

  Ce papier s'intéresse aux liens entre deux concepts : d'une part le clustering de graphes, mesuré par la modularité de Newman, et d'autre part le clustering d'un espace métrique, mesuré par la somme des carrés des distances au barycentre des clusters. Nous montrons qu'en passant de l'espace à un graphe de façon "naturelle" (par boules unitaires) et en appliquant un algorithme "naturel" de clustering (par $r$-net), on obtient un clustering de modularité bornée inférieurement (en fonction de la dimension de grille de l'espace et pour certains rayons de $r$-net). Quelques simulations en espace euclidien viennent illustrer le propos en comparant deux algorithmes pour les deux mesures de qualité.

  @InProceedings{msv11a,
  author = {de Montgolfier, Fabien AND Soto, Mauricio AND Viennot, Laurent},
  title = {Clustering de m\'etrique et clustering de graphe},
  booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (ALGOTEL)},
  pages = {1--4},
  year = 2011, x-language = {FR},
  x-international-audience = {NO},
  x-country = {FR},
  address = {Cap Est\'erel}
  }
• Autour du caractère arborescent d'Internet. Fabien de Montgolfier, M. S. et Laurent Viennot. MajecSTIC 2010, Bordeaux, France, October 2010. Abstract Bibtex Pdf

  Nous étudions le caractère arborescent d'Internet selon deux paramètres: la largeur arborescente et l'hyperbolicité. Nous approximons ces paramètres sur les graphes obtenus de sources différentes: CAIDA, Rocketfuel et l'Université de Strasbourg; et tant au niveau des AS que des routeurs. D'une part, la largeur arborescente d'Internet apparaît être élevée, reflétant une forte connectivité et prouvant l'existence d'un coeur bien connecté. D'autre part, l'hyperbolicité (en tant que paramètre du graphe) semble apparaître très faible, reflétant une structure d'arbre par rapport à la métrique. En outre, nous calculons la largeur arborescente et l'hyperbolicité pour des modèles classiques d'Internet.

  @InProceedings{msv09,
  author = {de Montgolfier, Fabien AND Soto, Mauricio AND Viennot, Laurent},
  title = {Autour du caract\`ere arborescent d'Internet},
  booktitle = {(MAnifestation des JEunes Chercheurs en Sciences et Technologies de l'Information et de la Communication (MajecSTIC) },
  year = {2009},
  address = {Bordeaux},
  country = {France},
  month = {Mai}
  }

In progress.

• On computing graph Hyperbolicity. Fabien de Montgolfier, M. S. et Laurent.

selected Talks

• p-Box: A “new” graph model. LIAFA, Université Paris Diderot, France, March 17, 2015. Pdf
• Asymptotic modularity of some graph classes. LIFO, Université d'Orléans. Orléans, France, July 2nd, 2012. Pdf
• On topological graph properties and applications to communication networks. Algorithms, Games, Combinatorics and Optimization Initiative, Universidad de Chile. Santiago, Chile, January 04, 2012. Pdf
• Clustering de Métrique et Clustering de Graphe (in french). AlgoTel'11. Cap Estérel, France, Mai 2011. Pdf
• Autour le caractère arborescente d'Internet (in french). Majecstics'10. Bordeaux, France, October 13, 2010. Pdf
• Adversarial Queueing Theory with Setups. Journée GANG, INRIA Rocquencourt. Paris, France, February 18, 2010. Pdf
• Treewidth and Treelength of Internet. ALADDIN Meeting. Poitiers, France, 20 November 2008. Pdf

Teaching