Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

WB6 Graphes / Graphs

9 mai 2012 11h00 – 12h15

Salle: Société canadienne des postes

Présidée par Adel Bessadok

3 présentations

  • 11h00 - 11h25

    Minimizing Crossings and Overlaps in Graph Embeddings

    • Amina Shabbeer, prés., Rensselaer Polytechnic Institute
    • Kristin P. Bennett, Rensselaer Polytechnic Institute

    We propose a novel continuous optimization based approach for graph drawing that can incorporate
    criteria such as avoidance of overlap of graph objects such as nodes, edges, or subgraphs and establish minimal distance between these objects. Scalable solutions using alternating directions of multiplier methods are proposed.

  • 11h25 - 11h50

    Lobster, Spider, Caterpillar and other Trees

    • Hélène-Sarah Bécotte-Boutin, prés., HEC Montréal

    When working on a special kind of graph, a researcher often wants to know if some literature already exists on that topic. Indeed, it is not easy to search for some literature on a given family of graph without knowing its name, which is likely a reason why some families of graphs are already known with various names. To handle this problem, we propose a tool that could be used to find the name(s) of a graph given its description. Because there are a lot of graphs, it would have been hard to characterize them all at the same time. For that reason, we started to characterize one special kind of graph first, which is the tree. The lobster, the spider and the caterpillar are a few families of trees. In this talk, those families and some other
    ones will be presented and characterized.

  • 11h50 - 12h15

    Social Network Analysis and the EMVNS Algorithm

    • Adel Bessadok, prés., Institut supérieur de gestion de Gabès
    • Pierre Hansen, HEC Montréal

    The big success role played by online Social Networks such as Facebook and Twitter in what we called « The Arabic Spring » and the consequent availability of social network data had pressed many scientific around the world to take more advantage in studying Social Network Analysis. Networks have been used to analyze interpersonal social relationships, communication networks, academic paper coauthorships and citations, and much more. Understanding the structure of these networks is one of the outstanding challenges in the study of complex systems. In this paper we focus on detecting structural features in large-scale network data using the machinery of probabilistic Mixture Models and the Expectation–Maximization (EM) algorithm. However EM is an iterative algorithm and it is very sensitive of the choice of initial values that can severely affect the time to attain convergence of the algorithm and its efficiency in finding an appropriate optimization for constructing proper statistical models of the data. We alleviate this defect by embedding the EM algorithm within the variable Neighborhood Search (VNS) methaheurestic framework.