社团发现的图挖掘算法及其并行化以及应用研究

As the regular data structure, graphs are playing a more and more important role in the modeling of complicated structures and also the reciprocal interaction. Graph mining has become one significant research task of tremendous momentum in the work of data mining. This task is to realize the overall objective through the resolution provided for the rapid identification and detection problem for one or more types of communities based on the application of non-frequent sub-graph model, and to research the Graph partitioning algorithm of the BSP model-based the Max-flow Min-cut Theorem in order to improve the efficiency of resolving issues of the max flow for large-scale or ultra-large-scale data flow diagrams, besides this method will also be applied to the research for communities detection thus to adapt to problems concerning the rapid processing and mining of big data due to the rapid development of the social network or SNSs; the Multi dimensional attribute-weight graph will also be proposed, based on the theoretical research of Multi dimensional attribute-weight graph, identification and detect method, mechanism and algorithm will also be explored based on the plain community density theories; meanwhile further research based on the application of those above-mentioned algorithms to continue the multi-scale and multi-granularity discovery research of communities will also be conducted so as to study on the communities discovery of SNSs, segmentation and discovery research based on those small-to-micro-scale communities based on the dimensions of nodes and the reciprocal relationship for the discovery of multi-attribute and multi-relation factors in the process of figuring out the compatibility of terroristic organization, besides in application to resolve these graph modeling and mining problems of complicated problems and to verify those theories and practice value and availability of the algorithms will also be fulfilled thus to provide a new path to the further development of graph mining.

图作为常用数据结构在复杂结构及其相互作用的建模中愈发重要。图挖掘已经成为数据挖掘中活跃而重要的课题。本课题以运用非频繁子图模式解决一类或若干类社团的快速识别与发现问题作为总体目标，研究基于BSP模式的并行最大流/最小割理论的图划分算法，提升针对大规模和超大规模数据图最大流求解的效率，并将其运用于社团发现研究中，以适应迅猛发展的社会网络、社交网络等带来的大数据快速处理和挖掘问题；提出并定义多维属性-权值图，基于多维属性-权值图的理论研究，探索新的基于朴素的社团密度思想的社团的识别和发现方法、机制与算法；同时致力于运用上述算法进行多尺度、多粒度的社团发现研究，探索在实际的社交网络的进行社团发现、基于节点属性与相互关系的小微社团的细分与发现研究，有助于在大的社交网络中发现恐怖组织等小微社团，在应用研究中解决复杂问题的图建模挖掘问题，检验算法的理论和实用价值及可用性，为图挖掘的进一步发展提供新思路

社团发现通常可以从两方面出发：网络结构和节点属性，本课题主要针对目前社团发现重视网络结构而忽视网络节点的现状进行图的多维属性-权值模型研究，并基于此模型进行社团发现算法研究以及相关的应用研究。具体来讲，主要研究内容包括：图的多维属性-权值模型；基于图多维属性-权值模型的LPA社团发现算法；社团节点影响力在网络控制中的应用；社团发现算法在中医方剂学中类方的应用研究。.主要研究结论：.1）建立了图的多维属性-权值模型，该模型是后续三个具体研究的基础。以节点具有的不同属性入手，可以定义基于属性的边的权值，可以定义节点在不同场景下的影响力，即魅力值。可以定义方剂社团中节点方剂之间的距离关系。.2）基于属性的边的权值，我们改进了LPA社团发现算法。实验结果表明，该改进算法运行时间与迭代次数略优于原算法，具有较高的鲁棒性，防止了平凡解的出现。 .3）基于节点的影响力，本项目研究了节点影响力在网络控制中的应用。提出了基于博弈论的接入控制算法，保证用户能够保持较好的用户体验，并且尽量减少禁止发送信息的用户的数量，算法在集中式拓扑网络中提升用户体验的幅度高于分散式拓扑网络。进一步地，本项目将此研究成果应用在移动医疗网络中，解决了通信网络中用户功率控制和入网机制应用于移动医疗时存在的问题，允许基于不完整信道信息的新型用户功率控制和入网控制方法。.4）基于方剂的不同组成成分以及不同成分中药药物的属性（四气五味、升降沉浮、归经、功能等）差异，定义方剂之间的距离。这种距离比单纯使用组成成分定义的距离更能体现方剂之间的实际临床应用中的异同。从研究结果来看，《伤寒论》方剂的类方划分结果与传统的人为划分结果不尽相同，但是，这种划分并不违反中医的基本理论和实践。划分结果说明了这种方法是可行的，与之前的方剂研究相比，这种方法对于方剂发展的源流研究，对于中医理论的深入研究都有重要意义，前途不可限量。