复杂多属性网络中的结构模式及其语义检测方法研究

A substantial amount of real-world problems can be represented by graphs, with abundant attributes associated with their vertices and edges. Posing enormous challenges to deal with those networks, the attributes contained in those networks are also valuable sources for mining their intrinsic structural patterns and semanteme. Our project centers around multi-attribute networks. We examine, analyze and understand the structural patterns and the semanteme involved. Besides we detect anomalies fast and accurately. We also seek to investigate the rule governing their evolution, comprehend their corresponding functions and discover their intrinsic patterns. We design an attribute-network-oriented approach that is able to find semanteme community by exploring the connection between attributes and communities. We devise an attribute-network-oriented method that can identify anomalous nodes and subgraphs by examining their attribute-network characteristics. We reveal the evolving patterns of entity relationship by studying the changing relationship among entities within dynamic attribute networks and the alteration of their topology. We develop a tendency subgraph discovery algorithm that is targeted at dynamic attribute networks by investigating the impact of variation of attribute values on structure changes and the interplay between nodes during their evolution within dynamic networks. Moreover, we also deliver a software package of algorithm that is efficient in time and in space, scalable, robust, requires the least manual intervention and can be extensively applied in the analysis of a wide range of real-world attribute networks.

现实生活中的很多问题可以建模为图结构，且其节点和边上带有丰富的属性标签信息。这些属性网络中所包含的大量属性信息对于挖掘其中内在结构模式及语义有重要价值，也给此类网络的分析和处理带来巨大的挑战。本项目以多属性网络为研究对象，深入检测、分析和挖掘多属性网络中的结构模式及其语义，准确、快速地检测异常，挖掘其内在模式、理解其功能特性、发现其演化规律。通过分析属性信息与社团的联系，设计面向属性网络的语义社团检测方法；通过分析属性网络特征，设计实现面向属性网络的异常结点及异常子图识别方法；通过分析动态属性网络实体间的关系演化及拓扑结构的变化情况，挖掘实体关系演化模式；通过分析动态属性网络中的属性值变化对结构改变及演化过程中结点间的相互作用情况，设计针对动态属性网络的趋势子图发现算法。设计实现时空效率高、用户较少干预、可伸缩性强、鲁棒性好的算法软件包，使其能广泛用于分析各种真实的属性网络。

现实生活中的很多问题可以建模为图结构，且其结点和边上带有丰富的属性信息。这些属性网络中包含的大量属性信息对于挖掘其内在结构模式及语义有重要价值，同时也给此类网络的分析和处理带来巨大的挑战。本项目以多属性网络为研究对象，深入检测、分析和挖掘多属性网络中的结构模式及其语义。本项目的主要研究内容包括：1、大规模属性网络上的社团检测问题；2、大规模属性网络上的社团搜索问题；3、大规模网络上的子图挖掘问题；4、社交网络上的团队形成问题；5、复杂道路网络上的目的地预测问题。.主要的研究进展包括：（1）提出了利用图分割方法将大规模属性网络划分为规模相近的子图进而并行化地进行社团检测的方法。同时，针对属性网络设计了结合属性信息的社团检测算法。（2）在属性图上提出在给定多个查询结点情况下的属性社团搜索问题，使用边连通性作为结构紧密性约束，并设计属性函数来衡量结点属性的紧密性。（3）提出了一种高效的挖掘k边连通分量的算法，解决了现有算法时间复杂度高，精确度低的问题。（4）深入研究了社交网络中的团队形成问题，提出了相应的解决算法，并在此基础上解决了对不同用户选择的社交事件进行组织的问题。（5）提出了一种首先确定最可能的未来位置然后预测目的地的方法，设计了一种新的未来轨迹预测方法，通过将转移概率和最可能的未来位置结合起来预测目的地。.针对所提出方法，项目进行期间共获得专利1项，发表学术论文21篇。其中SCI检索论文14篇，EI检索论文1篇。协助培养博士研究生2名，硕士研究生5名。 .项目的研究成果对于揭示属性网络的内在拓扑结构、理解其功能特性等均有十分重要的理论意义，此外对于丰富和完善复杂网络分析、图挖掘以及模式识别等相关领域的基础理论也具有积极的推动作用。