Incluant une Journée industrielle de l'optimisation
HEC Montréal, 7 - 9 mai 2012
JOPT2012
HEC Montréal, 7 — 9 mai 2012
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
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
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
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.