图学在人类文明进展中的作用研究

世界5大文明中心古老的文字都起源于图,图在人类文明进展中起很大作用并占重要地位.论述了古汉语象形文字、古埃及象形文字、古印度印章象形文字、中美洲玛雅象形文字、苏美尔楔形文字等世界文明中心文字的起源与图的关系.认为图学在人类文明进展中的核心作用是由“灵魂、主体、精髓、基础”构成的.物质形态与宇宙同生并存,图学具有叙述苍穹变化规律、承载人类文明信息、展示人类创新文明的重要功能.图学发展伴随着人类文明的过去、现在和未来,当代图学要真正承担起认识世界、传承文明、创新理论、咨政育人、服务社会、创新文化的神圣职责.     

Partitioning road networks using density peak graphs: Efficiency vs. accuracy

Road traffic networks are rapidly growing in size with increasing complexities. To simplify their analysis in order to maintain smooth traffic, a large urban road network can be considered as a set of small sub-networks, which exhibit distinctive traffic flow patterns. In this paper, we propose a robust framework for spatial partitioning of large urban road networks based on traffic measures. For a given urban road network, we aim to identify the different sub-networks or partitions that exhibit homogeneous traffic patterns internally, but heterogeneous patterns to others externally. To this end, we develop a two-stage algorithm (referred as FaDSPa) within our framework. It first transforms the large road graph into a well-structured and condensed density peak graph (DPG) via density based clustering and link aggregation using traffic density and adjacency connectivity, respectively. Thereafter we apply our spectral theory based graph cut (referred as α-Cut) to partition the DPG and obtain the different sub-networks. Thus the framework applies the locally distributed computations of density based clustering to improve efficiency and the centralized global computations of spectral clustering to improve accuracy. We perform extensive experiments on real as well as synthetic datasets, and compare its performance with that of an existing road network partitioning method. Our results show that the proposed method outperforms the existing normalized cut based method for small road networks and provides impressive results for much larger networks, where other methods may face serious problems of time and space complexities.     

Output consensus for multiple non-holonomic systems under directed communication topology

In this paper, the problem of output consensus for multiple non-holonomic systems in chained form has been investigated. First, an output consensus controller under the strongly connected communication topology is devised by two steps, where a time-varying control strategy and the backstepping design technique are employed. Then, the results are extended to the general directed topology case via graph decomposition, in which the input-to-state stability theory plays a critical role. We prove that the proposed controller can achieve the semi-global output consensus among multiple non-holonomic systems, provided that the interaction graph contains a spanning tree. Finally, numerical examples are provided to illustrate the effectiveness of the designed controller.     

Scale independent surface characterisation: Geography meets precision surface metrology

The recently published standard ISO 25178-2 distinguishes between field parameters and feature parameters for surface texture characterisation, whereby the main difference between these two types is due to the fact that the parameters belonging to the first group are deduced from all points of a scale-limited surface, while the parameters belonging to the second group are deduced from only a subset of predefined topological surface features. As specified in ISO 25178-2, two prerequisites are indispensable for the determination of the feature parameters, viz., an adequate data structure for surface characterisation and a suitable formal method for surface generalisation, i.e. for the successive elimination of the less important surface features. Within ISO 25178-2 change trees are proposed for describing the surface topography, while Wolf pruning is suggested for surface simplification (cf. also ISO 16610-85). Apart from the techniques specified in ISO 25178-2 and ISO 16610-85, the present paper describes a second geometrical–topological approach for the characterisation and generalisation of surfaces that has its origin within the geosciences and is based on weighted surface networks and w-contractions. In addition, it is revealed how the two approaches, both of which have their foundations in graph theory, are interrelated to each other and how, from a historical point of view, the GIScience approach forms the basis of the one applied within surface metrology. Finally, some applications within precision engineering are described.     

基于网络拓扑特性的MCI分类

阿尔茨海默氏病(Alzheimer's disease,AD)和轻度认知障碍(Mild cognitive impairment,MCI)是经常发生在老年人中的脑疾病,其主要表现为认知和智力的障碍.机器学习和模式识别方法已经被应用到对AD和MCI的诊断和分类中.最近,研究人员提出利用大脑连接网络实现对疾病的诊断和分类.大部分的研究主要集中在网络中提取一些局部的特性(如聚类系数),并利用机器学习的方法(如支持向量机)来实现对疾病的分类.然而,存在的研究表明AD以及MCI是和一个大规模的脑连接网络相关,而不仅是大脑的若干区域.因此,本文提出一种新的基于网络整体拓扑结构信息的分类方法,并将其用于对MCI疾病的分类.实验结果表明,本文的方法能够对分类结果有重要的改进.     

基于图论的市政排水设计软件基础研究和开发

在进行市政排水的设计开发中，将图论作为主要的数据结构进行开展，使得排水系统更加具有模块功能，并且将相关排水工程的 CAD 软件进行更大规模的开发。最终提高了工作的效率和质量，能够让相关工程人员实现更加便利的设计。     

BGNN: Behavior-aware graph neural network for heterogeneous session-based recommendation

Session-based recommendation (SBR) and multi-behavior recommendation (MBR) are both important problems and have attracted the attention of many researchers and practitioners. Different from SBR that solely uses one single type of behavior sequences and MBR that neglects sequential dynamics, heterogeneous SBR (HSBR) that exploits different types of behavioral information (e.g., examinations like clicks or browses, purchases, adds-to-carts and adds-to-favorites) in sequences is more consistent with real-world recommendation scenarios, but it is rarely studied. Early efforts towards HSBR focus on distinguishing different types of behaviors or exploiting homogeneous behavior transitions in a sequence with the same type of behaviors. However, all the existing solutions for HSBR do not exploit the rich heterogeneous behavior transitions in an explicit way and thus may fail to capture the semantic relations between different types of behaviors. However, all the existing solutions for HSBR do not model the rich heterogeneous behavior transitions in the form of graphs and thus may fail to capture the semantic relations between different types of behaviors. The limitation hinders the development of HSBR and results in unsatisfactory performance. As a response, we propose a novel behavior-aware graph neural network (BGNN) for HSBR. Our BGNN adopts a dual-channel learning strategy for differentiated modeling of two different types of behavior sequences in a session. Moreover, our BGNN integrates the information of both homogeneous behavior transitions and heterogeneous behavior transitions in a unified way. We then conduct extensive empirical studies on three real-world datasets, and find that our BGNN outperforms the best baseline by 21.87%, 18.49%, and 37.16% on average correspondingly. A series of further experiments and visualization studies demonstrate the rationality and effectiveness of our BGNN. An exploratory study on extending our BGNN to handle more than two types of behaviors show that our BGNN can easily and effectively be extended to multi-behavior scenarios.     

Model for flexibility evaluation in manufacturing network strategic planning

In response to market pressures, manufacturers have adopted different approaches to provide flexibility regarding several aspects. In this paper, we suggest a model for the evaluation of the flexibility of the manufacturing supply chain, based on graph theory techniques. This model defines maximum excess demand that may be met using flexibility. Recourse to flexibility enablers is determined based on cost minimisation. Such enablers are volume flexibility, mix flexibility and safety stocks. The proposed model is solved using a two-step Mix Integer Linear Programme; the first step consists in defining maximum demand that may be met while the second step concerns minimising cost. The main benefit of our model is to deal with realistic problems in a rather short time. Therefore, it can be used in a wide ‘what-if’ design process. It means evaluating various contemplated flexibility configurations in multiple demand scenarios in order to choose the best option. It can be also used during operational supply chain planning in order to face to an unbalanced situation. This paper ends with a numerical example illustrating our model’s efficiency.     

Design of reliable fiber‐based distribution networks modeled by multi‐objective combinatorial optimization

In this work, we investigate the planning of hybrid fiber/very high bit rate digital subscriber line (HFV) access networks. This HFV variant is considered as an alternative to passive optical access network. It consists of implementing optical fibers in the access network part from the central office to the street cabinets, whereas the very high bit rate digital subscriber line technology is used in the last meter part, from street cabinets to subscribers. Firstly, we discuss the different tasks of this planning problem. We model this planning problem as a multi‐objective optimization problem, where different conflicting objectives have to be optimized at the same time. We consider network costs and network reliability. This problem is solved by two different approaches: the classical single‐objective optimization (SOO) and the multi‐objective optimization (MOO), which is a recent optimization approach that is gaining an increasing interest in practical optimization problems. MOO solves the problem by searching for different optimal trade‐offs between the optimization objectives. The performances of SOO and MOO are analyzed and compared with each other using three network instances. Copyright © 2012 John Wiley & Sons, Ltd.     

A note on total colorings of 1-planar graphs

A 1-planar graph is a graph that can be drawn in the plane such that each edge is crossed by at most one other edge. In this paper we give an upper bound for the total chromatic number for 1-planar graphs with maximum degree at least 10.