Research and advances on graph data mining

doi:10.3724/SP.J.1087.2012.00182

Abstract

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

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

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

CLC Number:

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.

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

References

［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]	Yuxin HUANG, Jialong XU, Zhengtao YU, Shukai HOU, Jiaqi ZHOU. Unsupervised text sentiment transfer method based on generation prompt [J]. Journal of Computer Applications, 2024, 44(9): 2667-2673.
[2]	Shunyong LI, Shiyi LI, Rui XU, Xingwang ZHAO. Incomplete multi-view clustering algorithm based on self-attention fusion [J]. Journal of Computer Applications, 2024, 44(9): 2696-2703.
[3]	Chun SUN, Chunlong HU, Shucheng HUANG. Consistency preserving age estimation method by ensemble ranking [J]. Journal of Computer Applications, 2024, 44(8): 2381-2386.
[4]	Qiangkui LENG, Xuezi SUN, Xiangfu MENG. Oversampling method for imbalanced data based on sample potential and noise evolution [J]. Journal of Computer Applications, 2024, 44(8): 2466-2475.
[5]	Quanmei ZHANG, Runping HUANG, Fei TENG, Haibo ZHANG, Nan ZHOU. Automatic international classification of disease coding method incorporating heterogeneous information [J]. Journal of Computer Applications, 2024, 44(8): 2476-2482.
[6]	Ying YANG, Xiaoyan HAO, Dan YU, Yao MA, Yongle CHEN. Graph data generation approach for graph neural network model extraction attacks [J]. Journal of Computer Applications, 2024, 44(8): 2483-2492.
[7]	Qing WANG, Jieyu ZHAO, Xulun YE, Nongxiao WANG. Enhanced deep subspace clustering method with unified framework [J]. Journal of Computer Applications, 2024, 44(7): 1995-2003.
[8]	Dongwei WANG, Baichen LIU, Zhi HAN, Yanmei WANG, Yandong TANG. Deep network compression method based on low-rank decomposition and vector quantization [J]. Journal of Computer Applications, 2024, 44(7): 1987-1994.
[9]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.
[10]	Junchi GE, Weihua ZHAO. Distance weighted discriminant analysis based on robust principal component analysis for matrix data [J]. Journal of Computer Applications, 2024, 44(7): 2073-2079.
[11]	Qianhui LU, Yu ZHANG, Mengling WANG, Tingwei WU, Yuzhong SHAN. Classification model of nuclear power equipment quality text based on improved recurrent pooling network [J]. Journal of Computer Applications, 2024, 44(7): 2034-2040.
[12]	Xun YAO, Zhongzheng QIN, Jie YANG. Generative label adversarial text classification model [J]. Journal of Computer Applications, 2024, 44(6): 1781-1785.
[13]	Zixuan YUAN, Xiaoqing WENG, Ningzhen GE. Early classification model of multivariate time series based on orthogonal locality preserving projection and cost optimization [J]. Journal of Computer Applications, 2024, 44(6): 1832-1841.
[14]	Feiyu ZHAI, Handa MA. Hybrid classical-quantum classification model based on DenseNet [J]. Journal of Computer Applications, 2024, 44(6): 1905-1910.
[15]	Shibin LI, Jun GONG, Shengjun TANG. Semi-supervised heterophilic graph representation learning model based on Graph Transformer [J]. Journal of Computer Applications, 2024, 44(6): 1816-1823.