[1]施佺,肖仰华,鲁轶奇,等.基于摘要图的不确定社会网络Top-k子图查询算法[J].南京理工大学学报(自然科学版),2010,(06):738-743.
 SHI Quan,XIAO Yang-hua,LU Yi-qi,et al.Top-k Subgraph Query Algorithm on Uncertain Social Networks Based on Summary Graph[J].Journal of Nanjing University of Science and Technology,2010,(06):738-743.
点击复制

基于摘要图的不确定社会网络Top-k子图查询算法
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
期数:
2010年06期
页码:
738-743
栏目:
出版日期:
2010-12-31

文章信息/Info

Title:
Top-k Subgraph Query Algorithm on Uncertain Social Networks Based on Summary Graph
作者:
施佺;肖仰华;鲁轶奇;王恒山;
上海理工大学管理学院
Author(s):
SHI Quan12XIAO Yang-hua3LU Yi-qi3WANG Heng-shan1
1.School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China;2.School of Computer Science and Technology,Nantong University,Nantong 226019,China;3.School of Computer Science,Fudan University,Shanghai 200433,China
关键词:
社会网络 摘要图 Top-k查询
Keywords:
social networks summary graphs Top-k query
分类号:
O157.5
摘要:
针对不确定W eb社会网络的Top-k子图查询问题,以无向、顶点带标签及边赋权重的简单图为基本模型,设计了用来简洁描述社会网络并编码原始图信息的摘要图,提出了Top-k子图同构查询算法。针对真实和虚拟网络数据进行了大量实验,结果表明:基于摘要图的Top-k子图查询算法较VF2算法运算时间缩短;由于构建摘要图时的主要依据是顶点的标号,因此查询图的标号分布对查询性能有较大影响;顶点标号数目增加时该算法的查询性能呈类似指数形式提高,而VF2算法的查询性能没有受到较大影响;当数据图的顶点数量增大时,该算法与VF2算法相比,消耗时间的增长更缓慢;该算法在处理Top-k查询时体现出了稳定高效的性能。
Abstract:
Aimed at the Top-k subgragh query problem for an uncertain Web social network,with the basic model of an undirected,vertex labeled and edge weighted simple graph,a summary graph is designed to represent social networks and encode the information of original graphs.The Top-k subgraph isomorphism query algorithm is proposed.Extensive experimental results from real and synthetic network data show: the operation time of the Top-k subgraph query algorithm based on summary graphs decreases compared with the VF2 algorithm;because the main foundation to construct a summary graph is the label of a vertex,the label distribution of a query graph has a great effect on the query performance;the query performance of the algorithm is improved by the index method with the increase of the vertex label number,but the query performance of the VF2 algorithm is not influenced;with the increase of the number of vertexes,compared with the VF2 algorithm,the increase of the time consumption of the algorithm is slow;the algorithm has stable and efficient performance on Top-k query.

参考文献/References:

[ 1] Y an X F, Ph ilip S Y, H an JW. Graph index ing: Afrequent structure-based approach[ A] . Proceed ing s o fthe 2004 ACM S IGMOD Internationa l Conference onM anag em ent o f Data ( SIGMODc 04 ) [ C ]. Pa ris,Fance: ACM, 2004: 335- 346.
[ 2] Zhang S, HuM, Yang J. T reep:i A nove l graph indexing m ethod[ A]. Proceed ings of the 23rd Interna tionalCon fe rence on Data Eng ineering ( ICDEc07) [ C ].Istanbu,l Turkey: IEEE, 2007: 966- 975.
[ 3] Zhao P X, Yu J X, Yu P S. Graph index ing: tree +de lta> = graph[ A] . Proceedings o f the Internationa lCon ference on Very Large Data Bases ( VLDBc 07 )[ C] . V ienna, Austr ia: ACM, 2007: 938- 949.
[ 4] Fag in R, Lo tem A, NaorM. Optim a l aggrega tion a lgorithm s for m idd lew are [ J]. Journa l of Com pute r andSystem Sciences, 2003, 66( 4) : 614- 656.
[ 5] Chen C, Fredrikson C, Chr istodorescuM. M ining graphpatterns effic iently v ia random ized summ aries[ A]. Proceedings of the International Conference on Very LargeData Bases( VLDBc09) [ C]. Lyon, France: VLDB Endowmen,t 2009: 742- 753.
[ 6] Corde lla LP, Fogg ia P, Sansone C, e t a.l A ( Sub)g raph isom orph ism a lgor ithm form atch ing larg e g raphs[ J] . Journa l of Pattern Ana lysis andM ach ine Inte ll-igence, 2004, 26( 10): 1367- 1372

备注/Memo

备注/Memo:
基金项目: 国家自然科学基金( 61003001; 71071098); 江苏省自然科学基金( BK2009153; BK2010280) ; 南通市科技计划( K2008018; K2008031)作者简介: 施佺( 1973- ), 男, 博士生, 副教授, 主要研究方向: 图数据库、社会网络分析, E-m ail:shiquannt@gm a i.l com; 通讯作者: 王恒山( 1948- ), 男, 教授, 博士生导师, 主要研究方向: 复杂网络、管理信息系统, E-ma il:w anghs@ usst. edu. cn。
更新日期/Last Update: 2012-11-02