图数据挖掘技术的研究与进展

doi:10.3724/SP.J.1087.2012.00182

计算机应用 ›› 2012, Vol. 32 ›› Issue (01): 182-190.DOI: 10.3724/SP.J.1087.2012.00182

图数据挖掘技术的研究与进展

丁悦¹,张阳¹,²,李战怀³,王勇³

1. 西北农林科技大学信息工程学院，陕西杨凌 712100
2. 计算机软件新技术国家重点实验室(南京大学)，南京 210093
3. 西北工业大学计算机学院，西安 710072

收稿日期:2011-07-05 修回日期:2011-09-03 发布日期:2012-02-06 出版日期:2012-01-01
通讯作者: 张阳
作者简介:丁悦(1987-)，女，陕西西安人，硕士研究生，主要研究方向：图数据挖掘；张阳(1975-)，男，江苏扬州人，教授，博士生导师，博士，主要研究方向：数据挖掘、机器学习；李战怀(1961-)，男，陕西旬邑人，教授，博士生导师，博士，CCF高级会员，主要研究方向：数据库、网络存储、数据挖掘；王勇(1973-)，男，陕西临潼人，副教授，博士，主要研究方向：数据挖掘、机器学习。
基金资助:
国家自然科学基金资助项目(60901078);中央高校基本科研业务费专项(GK361001)

Research and advances on graph data mining

DING Yue¹,ZHANG Yang¹,²,LI Zhan-huai³,WANG Yong³

1. College of Information Engineering, Northwest A&F University, Yangling Shaanxi 712100, China
2. State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing Jiangsu 210093, China
3. School of Computer Science and Technology, Northwestern Polytechnical University, Xi'an Shaanxi 710072, China

Received:2011-07-05 Revised:2011-09-03 Online:2012-02-06 Published:2012-01-01
Contact: ZHANG Yang

摘要/Abstract

摘要： 生物信息学(蛋白质结构分析、基因组识别)、社会网络(实体间的联系)、Web分析(Web链接结构分析、Web内容挖掘和Web日志搜索)以及文本信息检索等的迅速发展积累了大量图数据，对于图数据的挖掘逐渐成为研究领域的热点。一些诸如聚类、分类、频繁模式挖掘的传统数据挖掘研究逐渐拓展到图数据领域。通过介绍现阶段图数据挖掘技术的研究进展，总结了图数据挖掘的特点、现实意义、主要问题以及应用场景，讨论并预测了图数据，尤其是不确定图数据研究的发展趋势和热点。

关键词: 数据挖掘, 图数据, 聚类, 分类, 频繁模式, 不确定图

Abstract: With the rapid growth of bioinformatics (protein structure analysis, genome identification), social networks (links between entities), Web analysis (interlinkage structure analysis, content mining and Web log retrieval), as well as the complex structure of text information retrievals, mining graph data has become a hot research field in recent years. Some traditional data mining algorithms have been gradually extended to graph data, such as clustering, classification, and frequent pattern mining. In this paper, the authors presented several state-of-art mainstream techniques for mining graph data, and gave a comprehensive summary of their characteristics, practical significance, as well as real-life applications on mining graph data. Finally, several research directions on graph data, and particularly, uncertain graph data were pointed out.

Key words: data mining, graph data, clustering, classification, frequent pattern, uncertain graph

中图分类号:

丁悦张阳李战怀王勇. 图数据挖掘技术的研究与进展[J]. 计算机应用, 2012, 32(01): 182-190.

DING Yue ZHANG Yang LI Zhan-huai WANG Yong. Research and advances on graph data mining[J]. Journal of Computer Applications, 2012, 32(01): 182-190.

参考文献

［1］

CONTE D, FOGGIA P, SANSONE C, et al. Thirty years of graph matching in pattern recognition ［J］. International Journal of Pattern Recognition and Artificial Intelligence, 2004, 18(3): 265-298.

［2］

CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub)graph isomorphism algorithm for matching large graphs ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(20): 1367-1372.

［3］

LARROSA J, VALIENTE G. Constraint satisfaction algorithms for graph pattern matching ［J］. Mathematical Structures in Computer Science, 2002, 12(4): 403-422.

［4］

MESSMER B T, BUNKE H. A decision tree approach to graph and subgraph isomorphism detection ［J］. Pattern Recognition, 1999, 32(12): 1979-1998.

［5］

LEVI G. A note on the derivation of maximal common subgraphs of two directed or undirected graphs ［J］. Calcolo, 1972, 9(4):341-354.

［6］

McGREGOR J J. Backtrack search algorithms and the maximal common subgraph problem ［J］. Software Practice and Experience, 1982, 12(1): 23-34.

［7］

BUNKE H, FOGGIA P, GUIDOBALDI C, et al. A comparison of algorithms for maximum common subgraph on randomly connected graphs ［C］// Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition. London: Springer-Verlag, 2002: 123-132.

［8］

BUNKE H, JIANG X, KANDEL A. On the minimum common supergraph of two graphs ［J］. Computing, 2000, 65(1):13-25.

［9］

SANFELIU A, FU K S. A distance measure between attributed relational graphs for pattern recognition ［J］. IEEE Transactions on Systems, Man, and Cybernetics: Part B, 1983, 13(3): 353-363.

［10］

MESSMER B T, BUNKE H. A new algorithm for error-tolerant subgraph isomorphism detection ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(5): 493-504.

［11］

WAGNER R A, FISCHER M J. The string-to-string correction problem ［J］. Journal of the Association for Computer Machinery, 1974, 21(1): 168-173.

［12］

MYERS R, WISON R C, HANCOCK E R. Bayesian graph edit distance ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(6): 628-635.

［13］

JUSTICE D, HERO A O. A binary linear programming formulation of the graph edit distance ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(8): 1200-1214.

［14］

BHALOTIA G, HULGERI A, NAKHE C, et al. Keyword searching and browsing in databases using BANKS ［C］// Proceedings of the 18th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2002: 431-440.

［15］

KACHOLIA V, PANDIT S, CHAKRABARTI S, et al. Bidirectional expansion for keyword search on graph databases ［C］// Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim: VLDB Endowment, 2005: 505-516.

［16］

HE HAO, WANG HAI-XUN, YANG JUN, et al. BLINKS: Ranked keyword searches on graphs ［C］// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2007: 305-316.

［17］

BALMIN A, HRISTIDIS V, PAPAKONSTANTINOU Y. Objec-tRank: Authority-based keyword search in databases ［C］// Proceedings of the 30th International Conference on Very Large Data Bases. Toronto: VLDB Endowment, 2004: 564-575.

［18］

INOKUCHI A, WASHIO T, OKADA T, et al. Applying the Apriori-based graph mining method to mutagenesis data analysis ［J］. Journal of Computer Aided Chemistry, 2001, 2(1): 87-92.

［19］

KURAMOCHI M, KARYPIS G. Frequent subgraph discovery ［C］// Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2001: 313-320.

［20］

VANETIK N, GUDES E, SHIMONY S E. Computing frequent graph patterns from semistructured data ［C］// Proceedings of the 2002 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2002: 458-465.

［21］

YAN XI-FENG, HAN JIA-WEI. gSpan: Graph-based substructure pattern mining ［C］// Proceedings of the 2002 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2002: 721-724.

［22］

HUAN JUN, WANG WEI, PRINS J. Efficient mining of frequent subgraphs in the presence of isomorphism ［C］// Proceedings of the 2002 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2002: 549-552.

［23］

YAN XI-FENG, HAN JIA-WEI. Closegraph: Mining closed fre-quent graph patterns ［C］// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2003: 286-295.

［24］

YAN XI-FENG, ZHOU X J, HAN JIA-WEI. Mining closed relational graphs with connectivity constraints ［C］// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York: ACM Press, 2005: 324-333.

［25］

COOK D J, HOLDER L B. Graph-based data mining ［J］. IEEE Intelligent Systems, 2000, 15(2): 32-41.

［26］

KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs ［J］. The Bell System Technical Journal, 1970, 49(1): 291-307.

［27］

BRODER A Z, CHARIKAR M, FRIEZE A, et al. Syntactic clustering of the Web ［C］// Proceedings of the 6th International Conference on World Wide Web. Essex, UK: Elsevier Science, 1997: 1157-1166.

［28］

GIBSON D, KUMAR R, TOMKINS A. Discovering large dense subgraphs in massive graphs ［C］// Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim: VLDB Endowment, 2005: 721-732.

［29］

FLAKE G, TARJAN R, TSIOUTSIOULIKLIS M. Graph clustering and minimum cut trees ［J］. Internet Mathematics, 2003, 1(4): 385-408.

［30］

AGGARWAL C, TA N, WANG JIAN-YONG, et al. XProj: A framework for projected structural clustering of XML documents ［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2007: 46-55.

［31］

LEE M, HSU W, YANG L, et al. XClust: Clustering XML schemas for effective integration ［C］// Proceedings of the 11th International Conference on Information and Knowledge Management. New York: ACM Press, 2002: 292-299.

［32］

WANG LIAN, CHEUNG D W, MAMOULIS N, et al. An efficient and scalable algorithm for clustering XML documents by structure ［J］. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(1): 82-96.

［33］

DALAMAGAS T, CHENG T, WINKEL K, et al. Clustering XML documents using structural summaries ［C］// Proceedings of the 2004 International Conference on Extending Database Technology. Berlin: Springer-Verlag, 2004: 547-556.

［34］

TSUDA K, KUDO T. Clustering graphs by weighted substructure mining ［C］// Proceedings of the 23rd International Conference on Machine Learning. New York: ACM Press, 2006: 953-960.

［35］

TSUDA K, KURIHARA K. Graph mining with variational Dirichlet process mixture models ［C］// Proceedings of the 8th SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics. New York: ACM Press, 2008: 432-442.

［36］

SAIGO H, NOWOZIN S, KADOWAKI T, et al. GBoost: A mathematical programming approach to graph classification and regression ［J］. Machine Learning, 2009, 75(1): 69-89.

［37］

DESHPANDE M, KURAMOCHI M, KARYPIS G. Frequent substructure based approaches for classifying chemical compounds ［J］. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(8): 1036-1050

［38］

MOONESINGHE H D K, VALIZADEGAN H, FODEH S, et al. A probabilistic substructure-based approach for graph classification ［C］// Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence. Washington, DC: IEEE Computer Society, 2007: 346-349.

［39］

HORVATH T, GARTNER T, WROBEL S. Cyclic pattern kernels for predictive graph mining ［C］// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2004: 158-167.

［40］

KASHIMA H, TSUDA K, INOKUCHI A. Marginalized kernels be-tween labeled graphs ［C］// Proceedings of the 21st International Conference on Machine Learning. New York: AAAI Press, 2003: 321-328.

［41］

BORGWARDT K M, KRIEGEL H P. Shortest-path kernels on graphs ［C］// Proceedings of the 5th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2005: 74-81.

［42］

ARTNER T G, FLACH P A, WROBEL S. On graph kernels: Hardness results and efficient alternatives ［C］// Proceedings of the 16th Annual Conference on Computational Learning Theory and the 7th Kernel Workshop. Berlin: Springer-Verlag, 2003: 129-143.

［43］

BOSER B E, GUYON I M, VAPNIK V N. A training algorithm for optimal margin classifiers ［C］// Proceedings of the Annual Conference on Computational Learning Theory. New York: ACM Press, 1992: 144-152.

［44］

WASSERMAN S, FAUST K. Social network analysis: Methods and applications ［M］. Cambridge: Cambridge University Press, 1995.

［45］

AGGARWAL C, WANG HAI-XUN. Managing and mining graph data ［M］. Berlin: Springer-Verlag, 2010.

［46］

RATTIGAN M, MAIER M, JENSEN D. Graph clustering with network structure indices ［C］// Proceedings of the 24th International Conference on Machine Learning. New York: ACM Press, 2007: 783-790.

［47］

GIBSON D, KUMAR R, TOMKINS A. Discovering large dense subgraphs in massive graphs ［C］// Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim: VLDB Endowment, 2005: 721-732.

［48］

ABELLO J, RESENDE M G, SUDARSKY S. Massive quasi-clique detection ［C］// Proceedings of the 5th Latin American Symposium on Theoretical Informatics. London: Springer-Verlag, 2002: 598-612.

［49］

PEI JIAN, JIANG DA-XIN, ZHANG AI-DONG. On mining cross-graph quasi-cliques ［C］// Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York: ACM Press, 2005: 228-238.

［50］

PEI JIAN, JIANG DA-XIN, ZHANG AI-DONG. Mining cross-graph quasi-cliques in gene expression and protein interaction data ［C］// Proceedings of the 21st International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2005: 353-354.

［51］

BORDINO I, DONATO D, GIONIS A, et al. Mining large net-works with subgraph counting ［C］// Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2008: 737-742.

［52］

CHAKRABARTI D, WANG YANG, WANG CHEN-XI, et al. Epidemic thresholds in real networks ［J］. ACM Transactions on Information Systems and Security, 2008, 10(4): 1-26.

［53］

LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks ［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2007: 420-429.

［54］

NEWMAN M E J. The spread of epidemic disease on networks ［M］. Maryland: American Physical Society, 2002.

［55］

BACKSTROM L, DWORK C, KLEINBERG J. Wherefore art thou r3579x? Anonymized social networks, hidden patterns, and structural steganography ［C］// Proceedings of the 16th International Conference on World Wide Web. New York: ACM Press, 2007: 181-190.

［56］

HAY M, MIKLAU G, JENSEN D, et al. Anonymizing social networks ［R］. Amherst, Massachusetts: University of Massachusetts, 2007: 7-19.

［57］

KLEINBERG J M. Challenges in mining social network data: Processes, privacy, and paradoxes ［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2007: 4-5.

［58］

HAY M, MIKLAU G, JENSEN D, et al. Resisting structural re-identification in anonymized social networks ［C］// Proceedings of the 34th International Conference on Very Large Data Bases. Berlin: Springer-Verlag, 2008: 102-114.

［59］

AGRAWAL R, SRIKANT R. Privacy-preserving data mining ［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2000: 439-450.

［60］

AGRAWAL D, AGRAWAL C. On the design and quantification of privacy preserving data mining algorithms ［C］// Proceedings of the 20th Symposium on Principles of Database Systems. New York: ACM Press, 2001: 247-255.

［61］

RUSSELL S, NORVIG P. Artificial intelligence: A modern approach ［M］. 3rd ed. Upper Saddle River: Prentice Hall, 2003.

［62］

YING XIAO-WEI, WU XIN-TAO, BARBARA D. Spectrum based fraud detection in social networks ［C］// Proceedings of the 17th ACM Conference on Computer and Communications Security. New York: ACM Press, 2010: 747-749.

［63］

YING XIAO-WEI, WU LE-TING, WU XIN-TAO. A spectrum-based framework for quantifying randomness of social networks ［J］. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(10): 912-923.

［64］

EICHINGER F, BOHM K, HUBER M. Improved software fault detection with graph mining ［EB/OL］. ［2011-04-04］. http://research.ics.tkk.fi/events/MLG08/papers/session3/paper21.pdf.

［65］

EICHINGER F, BOHM K, HUBER M. Mining edge-weighted call graphs to localize software bugs ［C］// Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer-Verlag, 2008: 333-348.

［66］

CHANG R-Y, PODGURSKI A, YANG JIONG. Discovering neglected conditions in software by mining dependence graphs ［J］. IEEE Transactions on Software Engineering, 2008, 34(5): 579-596.

［67］

ALTSCHUL S F, MADDEN T L, SCHEFFER A A, et al. Capped BLAST and PSI-BLAST: A new generation of protein database search programs ［J］. Nucleic Acids Research, 1997, 25(17): 3389-3402.

［68］

THOMPSON J D, HIGGINS D G, GIBSON T J. Clustalw: Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice ［J］. Nucleic Acids Research, 1994, 22(22): 4673-4680.

［69］

HARTWELL J H, HOPFIELD J J, LEIBLER S, et al. From molechlar to modular cell biology ［J］. Nature, 1999, 402(6761): C47-C51.

［70］

OLTVAI Z N,BARABASI A L. Life's complexity pyramid ［J］. Science, 2002, 298(5594): 763-764.

［71］

BORGELT C, BERTHOLD M R. Mining molecular fragments: Finding relevant substructures of molecules ［C］// Proceedings of 2002 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2002: 51-58.

［72］

DESHPANDE M, KURAMOCHI M, WALE N, et al. Frequent substructure-based approaches for classifying chemical compounds ［J］. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(8): 1036-1050.

［73］

HUAN JUN, WANG WEI, BANDYOPADHYAY D, et al. Mining spatial motifs from protein structure graphs ［C］// Proceedings of the 8th Conference on Research in Computational Molecular Biology. New York: ACM Press, 2004: 308-315.

［74］

KOYUTURK M, GRAMA A, SZPANKOWSKI W. An efficient algorithm for detecting frequent subgraphs in biological networks ［J］. Bioinformatics, 2004, 20(1): 200-207.

［75］

HU HAI-YAN, YAN XI-FENG, HUANG YU, et al. Mining coherent dense subgraphs across massive biological networks for functional discovery ［J］. Bioinformatics, 2005, 21(1): 213-221.

［76］

BARABASI A L, ALBERT R. Emergence of scaling in random networks ［J］. Science, 1999, 286(5439): 509-512.

［77］

FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power law relationships of the Internet topology ［C］// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York: ACM Press, 1999: 251-262.

［78］

FABRIKANT A, KOUTSOUPIAS E, PAPADIMITRIOU C H. Heuristically optimized trade-offs: A new paradigm for power laws in the Internet ［C］// Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Berlin: Springer-Verlag, 2002: 110-122.

［79］

KUMAR R, RAGHAVAN P, RAJAGOPALAN S, et al. Stochastic models for the Web graph ［C］// Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2000: 57-65.

［80］〖HJ1.5mm〗

BRIN S, PAGE L. The anatomy of a large scale hypertextual Web search engine ［C］// Proceedings of the 7th International Conference on World Wide Web 7. B. V. Amsterdam: Elsevier Science, 1998: 107-117.

［81］

PAGE L, BRIN S, MOTWANI R, et al. The pagerank citation ranking: Bringing order to the Web ［R］. Stanford: Stanford University, 1998.

［82］

BRODER A Z, GLASSMAN S C, MANASSE M S, et al. Syntactic clustering of the Web ［J］. Computer Networks and ISDN Systems, 1997, 29(8/9/10/11/12/13): 1157-1166.

［83］

BAEZA-YATES R, TIBERI A. Extracting semantic relations from query logs ［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2007: 76-85.

［84］

MEI QIAO-ZHU, ZHOU DENG-YONG, CHURCH K. Query suggestion using hitting time ［C］// Proceeding of the 17th ACM Conference on Information and Knowledge Management. New York: ACM Press, 2008: 469-478.

［85］

BONCHI F, CASTILLO C, DONATO D, et al. Topical query decomposition ［C］// Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2008: 52-60.

［86］

BOLDI P, BONCHI F, CASTILLO C, et al. The query-flow graph: Model and applications ［C］// Proceeding of the 17th ACM Conference on Information and Knowledge Management. New York: ACM Press, 2008: 609-618.

［87］

CAO HUAN-HUAN, JIANG DAX-IN, PEI JIAN, et al. Context-aware query suggestion by mining click-through and session data ［C］// Proceeding of the 14th ACM International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2008: 875-883.

［88］

WEN JI-RONG, NIE JIAN-YUN, ZHANG HONG-JIANG. Clustering user queries of a search engine ［C］// Proceedings of the 10th International Conference on World Wide Web. New York: ACM Press, 2001: 162-168.

［89］

FONSECA B M, GOLGHER P B, de MOURA E S, et al. Discovering search engine related queries using association rules ［J］. Journal of Web Engineering, 2004, 2(4):215-227.

［90］

BEEFERMAN D, BERGER A. Agglomerative clustering of a search engine query log ［C］// Proceedings of the 6th ACM International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2000: 407-416.

［91］

BAEZA-YATES R, HURTADO C, MENDOZA M. Query recommendation using query logs in search engines ［C］// Proceedings of the 2004 International Conference on Extending Database Technology. Berlin: Springer-Verlag, 2005: 395-397.

［92］

CASTILLO C, DONATO D, GIONIS A. Estimating the number of citations of a paper using author reputation ［C］// Proceedings of the 14th International Conference on String Processing and Information Retrieval. Berlin: Springer-Verlag, 2007: 107-117.

［93］

AGICHTEIN E, CASTILLO C, DONATO D, et al. Finding high quality content in social media, with an application to community-based question answering ［C］// Proceedings of the 4th ACM International Conference on Web Search and Data Mining. New York: ACM Press, 2008: 183-194.

［94］

ASTHANA S, KING O, GIBBONS F, et al. Predicting protein complex membership using probabilistic network reliability ［J］. Genome Research, 2004, 14(6): 1170-1175.

［95］

GHOSH J, NGO H Q, YOON S, et al. 〖HJ1.7mm〗On a routing problem within probabilistic graphs and its application to intermittently connected networks ［EB/OL］. ［2011-05-20］. http://joyghosh.com/docs/INFOCOM_SOLAR_ANAL.pdf.

［96］

INOKUCHI A, WASHIO T, MOTODA H. An Apriori-based algorithm for mining frequent substructures from graph data ［C］// Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery. Berlin: Springer-Verlag, 2000: 13-23.

［97］

NIJSSEN S, KOK J N. A quickstart in frequent structure mining can make a difference ［C］// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2004: 647-652.

［98］

HUAN JUN, WANG WEI, PRINS J, et al. Spin: Mining maximal frequent subgraphs from graph databases ［C］// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2004: 581-586.

［99］

周水庚,蔚赵春,蒋豪良.图结构数据搜索的概念、问题与进展［J］.中国计算机学会通讯,2007,3(8):59-65.

［100］

SHASHA D, WANG T L J, GIUGNO R. Algorithmics and application of tree and graph searching ［C］// Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM Press, 2002: 39-52.

［101］

YAN XI-FENG, YU P S, HAN JIA-WEI. Graph indexing: A frequent structure-based approach ［C］// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2004: 335-346.

［102］

ZOU ZHAO-NIAN, LI JIAN-ZHONG, GAO HONG, et al. Finding top-k maximal cliques in an uncertain graph ［C］// Proceedings of the 26th IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2010: 649-652.

［103］

HINTSANEN P. The most reliable subgraph problem ［C］// Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer-Verlag, 2007: 471-478.

［104］

de RAEDT L, KERSTING K, KIMMIG A, et al. Compressing probabilistic prolog programs ［J］. Machine Learning, 2008, 70(2/3): 151-168.

［105］

HINTSANEN P, TOIVONEN H. Finding reliable subgraphs from large probabilistic graphs ［J］. Data Mining and Knowledge Discovery, 2008, 17(1): 3-23.

［106］

COLBOURN C J. The combinatorics of network reliability ［M］. Oxford: Oxford University Press, 1987.

［107］

VALDES J, TARJAN R E, LAWLER E L. The recognition of series parallel digraphs ［J］. SIAM Journal on Computing, 1982, 11(2): 298-313.

［108］

ZOU ZHAO-NIAN, LI JIAN-ZHONG, GAO HONG, et al. Frequent subgraph pattern mining on uncertain graph data ［C］// Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York: ACM Press, 2009: 583-592.

［109］

张硕,高宏,李建中,等.不确定图数据库中高效查询处理［J］.计算机学报,2009,32(10):2066-2079.

［110］

邹兆年,李建中,高宏,等.从不确定图中挖掘频繁子图模式［J］.软件学报,2009,20(11):2965-2976.

［111］

HENDRIX W, SCHMIDT M C, BREIMYER P, et al. On perturbation theory and an algorithm for maximal clique enumeration in uncertain and noisy graphs ［C］// Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data. New York: ACM Press, 2009: 48-56.

［112］

ZHOU HAO, SHAVERDIAN A, JAGADISH H V. Querying graphs with uncertain predicates ［C］// Proceedings of the 8th Workshop on Mining and Learning with Graphs. New York: ACM Press, 2009: 163-170.

［113］

CHEN LEI, WANG CHANG-LIANG. Continuous subgraph pattern search over certain and uncertain graph streams ［J］. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(8): 1093-1109.

［114］

AGGARWAL C C, ZHAO YU-CHEN, YU P S. On clustering graph streams ［EB/OL］. ［2011-04-29］. http://www.siam.org/proceedings/datamining/2010/dm10_042_aggarwalc.pdf.

[1]	余敦辉, 万鹏, 王社. 基于企业知识图谱构建的实体关联查询系统[J]. 计算机应用, 2021, 41(9): 2510-2516.
[2]	宋中山, 梁家锐, 郑禄, 刘振宇, 帖军. 基于双向门控尺度特征融合的遥感场景分类[J]. 计算机应用, 2021, 41(9): 2726-2735.
[3]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[4]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[5]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[6]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[7]	朱亮, 徐华, 崔鑫. 基于基分类器系数和多样性的改进AdaBoost算法[J]. 计算机应用, 2021, 41(8): 2225-2231.
[8]	曾祥银, 郑伯川, 刘丹. 基于深度卷积神经网络和聚类的左右轨道线检测[J]. 计算机应用, 2021, 41(8): 2324-2329.
[9]	胡天杰, 胡文军, 王士同. 分布熵惩罚的支持向量数据描述[J]. 计算机应用, 2021, 41(8): 2212-2218.
[10]	尹春勇, 张帼杰. 面向分布式漂移数据流的集成分类模型[J]. 计算机应用, 2021, 41(7): 1947-1955.
[11]	肖振远, 王逸涵, 罗建桥, 熊鹰, 李柏林. 基于部分加权损失函数的RefineDet[J]. 计算机应用, 2021, 41(7): 1928-1932.
[12]	张洋, 江铭虎. 基于注意力机制的文本作者识别[J]. 计算机应用, 2021, 41(7): 1897-1901.
[13]	贾鹤鸣, 郎春博, 姜子超. 基于轻量级卷积神经网络的植物叶片病害识别方法[J]. 计算机应用, 2021, 41(6): 1812-1819.
[14]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[15]	章惠, 张娜娜, 黄俊. 优化LeNet-5网络的多角度头部姿态估计方法[J]. 计算机应用, 2021, 41(6): 1667-1672.

图数据挖掘技术的研究与进展

Research and advances on graph data mining

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics