Development of algorithms for the conception and the analysis of graphs and complex networks

开发图形和复杂网络的概念和分析算法

• 批准号: RGPIN-2015-04945
• 负责人: Caporossi, Gilles
• 金额: $ 1.6万
• 依托单位: HEC Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=678649
• 关键词: Development; algorithms; conception; analysis; graphs

A graph is a mathematical object consisting of vertices connected by edges if necessary. Graphs are useful for modeling some situations or to facilitate the visualization of complex data. ******My research project is related to the graphs, namely the search graph having desired characteristics, the study of particular graphs and the representation of complex information using graphs. ******1. Searching for extreme graphs ******Since my Ph.D, I work on finding extreme graphs, graphs that have special properties. Besides allowing to identify mathematical properties of graphs or finding results in mathematical chemistry (molecules may be represented by graphs), this approach recently allowed one of my students during his Ph.D., to find a family of graphs that correspond to a robust telecommunication networks. We plan to continue in this direction and use optimization for the design of telecommunications networks. There are still relevant applications in that field, however I am now considering extending my research area to some other, related problems. ******2. The study of complex networks ******Complex networks, such as social networks are typically graphs of large size. The complex network analysis is primarily based on two aspects: the identification of important vertices and communities detection. Identification of important vertices is based upon the centrality and allows the identification of individuals who have a key role. An application may be the viral marketing problem where the goal is to identify influent individuals. Communities detection in a network is an application of clustering, an area where I work for years. ******3. The representation of complex information ******The last point, the representation of complex information, is an area in which I entered during a recent work on the representation of the writing process. This process includes a temporal component and a spatial one. Some programs allow the recording of the activity of a person while she writes with a word processor or by hand with a graphical tablet. The records yield a large amount of data that is difficult to analyse by a human. We found that such data may be modelled by a graph. This is a new representation technique that is perceived by linguists, psychologists and educationalists as an advance toward a better understanding of the phenomenon. There are reasons to believe that such a representation could be extended to other processes involving space and time, with possible applications in industrial engineering.

一个图是一个数学对象，它由必要时由边连接的顶点组成。图形对于建模某些情况或促进复杂数据的可视化非常有用。** 我的研究项目与图有关，即具有所需特征的搜索图，特定图的研究以及使用图表示复杂信息。*1.寻找极端图 ** 自从我获得博士学位以来，我一直致力于寻找极端图，即具有特殊性质的图。除了允许识别图形的数学属性或在数学化学中找到结果（分子可以用图形表示），这种方法最近允许我的一个学生在他的博士学位期间，找到对应于鲁棒电信网络的图族。我们计划继续朝着这个方向发展，并将优化用于电信网络的设计。在这个领域仍然有相关的应用，但是我现在正在考虑将我的研究领域扩展到其他一些相关的问题。2.复杂网络的研究 * 复杂网络，如社交网络，通常是大尺寸的图。复杂网络分析主要基于两个方面：重要节点的识别和社区检测。重要顶点的识别基于中心性，并允许识别具有关键作用的个体。一个应用程序可能是病毒式营销问题，其目标是识别影响力的个人。网络中的社区检测是聚类的一个应用，我在这个领域工作了多年。3.复杂信息的表征 ** 最后一点，复杂信息的表征，是我在最近的一项关于写作过程表征的工作中进入的一个领域。这一过程包括一个时间分量和一个空间分量。有些程序允许记录一个人用文字处理器或手写板书写时的活动。这些记录产生了大量难以由人类分析的数据。我们发现，这些数据可以用图来建模。这是一种新的表征技术，被语言学家、心理学家和教育学家认为是对这一现象更好理解的一种进步。有理由相信，这种表示法可以扩展到其他涉及空间和时间的过程，并可能在工业工程中应用。