欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
紧密子图发现在许多现实世界网络应用中具有重要的研究意义．提出一种新的紧密子图发现问题——Top—k属性差异q—clique查询，找出图中k个节点间属性具有最大差异的q—clique．属性差异q-clique是一种结合图的结构特征和节点属性的紧密子图，在作者合作关系图数据中，该查询可以发现属性（如研究领域或所属单位）上不同的具有紧密合作关系的团队．给出了q-clique的属性差异度量，证明了该问题为NP难问题．采用分支限界策略，提出一种有效求解问题的算法AD—Qclique，同时依照best-first排序思想优化节点访问次序进一步提高算法性能．ACM作者信息数据集上的实验表明，算法AD—Qelique效率远优于基本算法BSL，并且结果中作者皆具有较高的Hindex值及广泛的研究领域．
英文摘要：
The problem of dense subgraph discovery has important research meanings in many applications in real-world networks. This paper discusses a new problem about dense subgraph discovery, Top-k attribute difference q-clique queries, to find k q-cliques in which the dissimilari- ty between each vertices＇ attribute is as large as possible. The attribute difference q-clique is a dense subgraph combining both the characters of structure and attributes content, and the queries will find teams in which members＇ attribute （e. g. , research field or affiliation） are different from each other in a co-authorship network. This paper gives the attribute difference measure of q- clique and shows the problem of finding the maximum-difference q-clique is NP-Hard. This paper proposes a query algorithm AD-Qclique for the problem of attribute difference q-clique by using branch and bound strategy and optimizes the node visit order according to best-first order. This paper conducts extensive experiments through ACM author information dataset, which show that AD-Qelique obtains an order of magnitude speed-up comparing to BSL and all the authors in the result set have high H-index value and wide field of study.
同期刊论文项目
同项目期刊论文
期刊信息
位置：