Article(id=1329457158091026749, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329457157424132411, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202440120, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1710432000000, receivedDateStr=2024-03-15, revisedDate=1715875200000, revisedDateStr=2024-05-17, acceptedDate=null, acceptedDateStr=null, onlineDate=1794896886608, onlineDateStr=2026-11-17, pubDate=1722441600000, pubDateStr=2024-08-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794896886608, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794896886608, creator=13701087609, updateTime=1794896886608, updator=13701087609, issue=Issue{id=1329457157424132411, tenantId=1146029695717560320, journalId=1324759914146529478, year='2024', volume='61', issue='8', pageStart='1863', pageEnd='2126', issueExtLink='null', onlineDate='null', pubDate='1722441600000', pubDateStr='2024-08-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794896886449, creator='13701087609', updateTime=1794896886449, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=1882, endPage=1903, ext={EN=ArticleExt(id=1329457158413988160, articleId=1329457158091026749, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Edge Hashing Distributed Sampling Algorithm for Triangle Counting in Large-scale Dynamic Graph Stream, columnId=1329457158304936255, journalTitle=Journal of Computer Research and Development, columnName=Special Issue on Graph Machine Learning, runingTitle=null, highlight=null, articleAbstract=
Triangle counting is a classical problem in large-scale graph analysis and widely applied in areas such as social network analysis, anomaly detection, and graph mining. In dynamic graph data streams, the topological structure of graph is constantly changing, involving edge insertions and deletions. Recent researches mainly focus on static streaming graphs and the corresponding streaming graph sampling algorithms only deal with edge insertions. Only a few single-machine sampling algorithms with low accuracy can handle edge deletion operations. We propose the edge hashing assignment-based distributed sampling (EHADS) algorithm, which is a distributed streaming algorithm designed for estimating the number of triangles in dynamic graph data streams. EHADS algorithm can rapidly and accurately estimate the counts of global triangles and local triangles associated with each vertex in dynamic streaming graphs. EHADS algorithm processes the input graph stream only once and samples edges across multiple machines. Compared with state-of-the-art single-machine streaming algorithms, the experimental results reflect that EHADS algorithm has the following advantages: 1) with the same sample capacity, EHADS algorithm achieves smaller estimation errors with less runtime, reducing the average estimation error of global triangle count by 31.79% and local triangle count by 23.35%; 2) EHADS algorithm provides unbiased estimations of the triangle count in streaming graph, and mathematical proofs demonstrate that the above-mentioned unbiased estimation has smaller variance.
, authors=Yulin He
1, 2, *, Bo Wu
2, Dingming Wu
2, Zhexue Huang
1, 2, Fournier-Viger Philippe
2, authorsList=Yulin He, Bo Wu, Dingming Wu, Zhexue Huang, Fournier-Viger Philippe, authorCompany=null, correspAuthors=Yulin He, authorNote=
born in 1982. PhD, research fellow. Member of CCF. His main research interests include data mining and machine learning, big data processing and analysis, big data approximate computing technology, and multi-sample statistic analysis theory and method
born in 2000. Master candidate. His main research interests include social network management and mining, big data system computing technologies, and machine learning algorithms and their applications
born in 1982. PhD, associate professor. Her main research interest includes the management and mining for spatial text data, knowledge graph data, social network data
born in 1959. PhD, professor, PhD supervisor. Member of CCF. His main research interests include data mining, machine learning, big data processing and analysis, and big data system computing technologies
born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include data mining, artificial intelligence, knowledge expression and inference, and cognitive model construction
, correspAuthorsNote=null, copyrightStatement=Copyright © 2024 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329457163552010607, articleId=1329457158091026749, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=针对大规模动态图流三角形计数的边哈希分布式抽样算法, columnId=1329457158523040065, journalTitle=计算机研究与发展, columnName=图机器学习专题, runingTitle=null, highlight=null, articleAbstract=
三角形计数是大图分析的一个经典问题,近年的研究工作主要集中在针对静态流式图的三角形数量估计上,相关流式图抽样算法只能处理边的插入操作,无法处理边的删除操作;而现有的动态流式图抽样算法估计准确性又偏低. 针对上述问题,提出了基于边哈希分配的分布式抽样(edge hashing assignment-based distributed sampling,EHADS)算法,它是一个用于估计动态流式图中三角形数量的分布式流算法,可以快速准确地估计动态流式图中的全局三角形数量以及每个顶点的局部三角形数量. EHADS算法只对输入的图流进行1次处理,并在多台机器上对边进行抽样. 与先进的单机流算法相比,EHADS算法具有2点优势:1)在相同样本容量的情况下,EHADS算法以更短的运行时间获得了更小的估计误差,估计全局三角形数量的误差平均降低了31.79%,估计局部三角形数量的误差平均降低了23.35%;2)EHADS算法能够提供流式图中三角形数量的无偏估计,并且严格的数学证明显示该无偏估计具有更小的方差.
, authors=何玉林
1, 2, *, 吴波
2, 吴定明
2, 黄哲学
1, 2, 菲律普弗尼尔-维格
2, authorsList=何玉林, 吴波, 吴定明, 黄哲学, 菲律普弗尼尔-维格, authorCompany=null, correspAuthors=何玉林, authorNote=
 |
1982年生. 博士,研究员. CCF会员. 主要研究方向为数据挖掘与机器学习、大数据处理与分析、大数据近似计算技术、多样本统计分析理论与方法 |
 |
2000年出生. 硕士研究生. 主要研究方向为社交网络的管理与挖掘、大数据系统计算技术、机器学习算法及其应用 |
 |
1982年生. 博士,副教授. 主要研究方向为空间文本数据、知识图谱数据、社交网络数据上的管理和挖掘 |
 |
1959年生. 博士,教授,博士生导师. CCF会员. 主要研究方向为数据挖掘、机器学习、大数据处理与分析、大数据系统计算技术 |
 |
1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为数据挖掘、人工智能、知识表示和推理、认知模型构建 |
, correspAuthorsNote=
, copyrightStatement=版权所有 © 2024 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=HDdQuvPNpCKhVlPRR81XRg==, magXml=Ewe/FeKmAqsC+GJ9HAPqyA==, pdfUrl=null, pdf=3FBQh7P7c1uW+LUB2mLU+Q==, pdfFileSize=3258525, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=t47Aa3zGVExSj/x0HYp0TA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=xtZtZksZSPmhicimu7jcWA==, mapNumber=null, fund=null)}, authors=[Author(id=1329457163992412537, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=yulinhe@gml.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329457164080492924, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457163992412537, language=EN, stringName=Yulin He, firstName=Yulin, middleName=null, lastName=He, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
1, 2, *, address=
1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, bio={"content":"
born in 1982. PhD, research fellow. Member of CCF. His main research interests include data mining and machine learning, big data processing and analysis, big data approximate computing technology, and multi-sample statistic analysis theory and method
"}, bioImg=null, bioContent=
born in 1982. PhD, research fellow. Member of CCF. His main research interests include data mining and machine learning, big data processing and analysis, big data approximate computing technology, and multi-sample statistic analysis theory and method
, aboutCorrespAuthor=null), CN=AuthorExt(id=1329457164147601790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457163992412537, language=CN, stringName=何玉林, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
1, 2, *, address=
1人工智能与数字经济广东省实验室(深圳) 广东深圳 518107
2深圳大学计算机与软件学院 广东深圳 518060, bio={"img":"iViAxge2V7HwX27X6VtfBg==","content":"
1982年生. 博士,研究员. CCF会员. 主要研究方向为数据挖掘与机器学习、大数据处理与分析、大数据近似计算技术、多样本统计分析理论与方法
"}, bioImg=iViAxge2V7HwX27X6VtfBg==, bioContent=
1982年生. 博士,研究员. CCF会员. 主要研究方向为数据挖掘与机器学习、大数据处理与分析、大数据近似计算技术、多样本统计分析理论与方法
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329457163828834674, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=1, ext=[AuthorCompanyExt(id=1329457163837223283, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107), AuthorCompanyExt(id=1329457163845611892, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1人工智能与数字经济广东省实验室(深圳) 广东深圳 518107)]), AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])]), Author(id=1329457165770797440, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wubo2022@email.szu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329457165850489219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457165770797440, language=EN, stringName=Bo Wu, firstName=Bo, middleName=null, lastName=Wu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, bio={"content":"
born in 2000. Master candidate. His main research interests include social network management and mining, big data system computing technologies, and machine learning algorithms and their applications
"}, bioImg=null, bioContent=
born in 2000. Master candidate. His main research interests include social network management and mining, big data system computing technologies, and machine learning algorithms and their applications
, aboutCorrespAuthor=null), CN=AuthorExt(id=1329457165921792388, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457165770797440, language=CN, stringName=吴波, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2深圳大学计算机与软件学院 广东深圳 518060, bio={"img":"nVDTVuaB3TzmoIbP00ltrg==","content":"
2000年出生. 硕士研究生. 主要研究方向为社交网络的管理与挖掘、大数据系统计算技术、机器学习算法及其应用
"}, bioImg=nVDTVuaB3TzmoIbP00ltrg==, bioContent=
2000年出生. 硕士研究生. 主要研究方向为社交网络的管理与挖掘、大数据系统计算技术、机器学习算法及其应用
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])]), Author(id=1329457165997289862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329457166089564552, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457165997289862, language=EN, stringName=Dingming Wu, firstName=Dingming, middleName=null, lastName=Wu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, bio={"content":"
born in 1982. PhD, associate professor. Her main research interest includes the management and mining for spatial text data, knowledge graph data, social network data
"}, bioImg=null, bioContent=
born in 1982. PhD, associate professor. Her main research interest includes the management and mining for spatial text data, knowledge graph data, social network data
, aboutCorrespAuthor=null), CN=AuthorExt(id=1329457166148284809, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457165997289862, language=CN, stringName=吴定明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2深圳大学计算机与软件学院 广东深圳 518060, bio={"img":"3+mQEIiwtdM/d+b9I1yVNw==","content":"
1982年生. 博士,副教授. 主要研究方向为空间文本数据、知识图谱数据、社交网络数据上的管理和挖掘
"}, bioImg=3+mQEIiwtdM/d+b9I1yVNw==, bioContent=
1982年生. 博士,副教授. 主要研究方向为空间文本数据、知识图谱数据、社交网络数据上的管理和挖掘
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])]), Author(id=1329457166248948107, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329457166337028494, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457166248948107, language=EN, stringName=Zhexue Huang, firstName=Zhexue, middleName=null, lastName=Huang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
1, 2, address=
1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, bio={"content":"
born in 1959. PhD, professor, PhD supervisor. Member of CCF. His main research interests include data mining, machine learning, big data processing and analysis, and big data system computing technologies
"}, bioImg=null, bioContent=
born in 1959. PhD, professor, PhD supervisor. Member of CCF. His main research interests include data mining, machine learning, big data processing and analysis, and big data system computing technologies
, aboutCorrespAuthor=null), CN=AuthorExt(id=1329457166395748751, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457166248948107, language=CN, stringName=黄哲学, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
1, 2, address=
1人工智能与数字经济广东省实验室(深圳) 广东深圳 518107
2深圳大学计算机与软件学院 广东深圳 518060, bio={"img":"R093/qtVy+tgzujEA67cfQ==","content":"
1959年生. 博士,教授,博士生导师. CCF会员. 主要研究方向为数据挖掘、机器学习、大数据处理与分析、大数据系统计算技术
"}, bioImg=R093/qtVy+tgzujEA67cfQ==, bioContent=
1959年生. 博士,教授,博士生导师. CCF会员. 主要研究方向为数据挖掘、机器学习、大数据处理与分析、大数据系统计算技术
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329457163828834674, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=1, ext=[AuthorCompanyExt(id=1329457163837223283, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107), AuthorCompanyExt(id=1329457163845611892, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1人工智能与数字经济广东省实验室(深圳) 广东深圳 518107)]), AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])]), Author(id=1329457166500606353, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329457166580298132, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457166500606353, language=EN, stringName=Fournier-Viger Philippe, firstName=Fournier-Viger, middleName=null, lastName=Philippe, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, bio={"content":"
born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include data mining, artificial intelligence, knowledge expression and inference, and cognitive model construction
"}, bioImg=null, bioContent=
born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include data mining, artificial intelligence, knowledge expression and inference, and cognitive model construction
, aboutCorrespAuthor=null), CN=AuthorExt(id=1329457166639018389, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, authorId=1329457166500606353, language=CN, stringName=菲律普弗尼尔-维格, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=
2, address=
2深圳大学计算机与软件学院 广东深圳 518060, bio={"img":"KtL5iLf48ke5SYzKJ+I6zg==","content":"
1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为数据挖掘、人工智能、知识表示和推理、认知模型构建
"}, bioImg=KtL5iLf48ke5SYzKJ+I6zg==, bioContent=
1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为数据挖掘、人工智能、知识表示和推理、认知模型构建
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])])], keywords=[Keyword(id=1329457166718710166, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, orderNo=1, keyword=triangle counting), Keyword(id=1329457166781624727, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, orderNo=2, keyword=dynamic graph stream), Keyword(id=1329457166840344984, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, orderNo=3, keyword=edge sampling), Keyword(id=1329457166899065241, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, orderNo=4, keyword=distributed streaming algorithm), Keyword(id=1329457166953591194, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, orderNo=5, keyword=edge hashing assignment), Keyword(id=1329457167029088667, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, orderNo=1, keyword=三角形计数), Keyword(id=1329457167092003228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, orderNo=2, keyword=动态图流), Keyword(id=1329457167154917789, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, orderNo=3, keyword=边抽样), Keyword(id=1329457167276552607, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, orderNo=4, keyword=分布式流算法), Keyword(id=1329457167343661472, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, orderNo=5, keyword=边哈希分配)], refs=[Reference(id=1329457171101757899, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Chung F R K, Lu L. Complex graphs and networks[M]. Rhode Island: American Mathematical Soc, 2006, articleTitle=null, refAbstract=null), Reference(id=1329457171168866764, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media?[C]//Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 591−600, articleTitle=null, refAbstract=null), Reference(id=1329457171240169933, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Newman M E J. Coauthorship networks and patterns of scientific collaboration[J]. Proceedings of the National Academy of Sciences, 2004, 101(suppl_1): 5200−5205, articleTitle=null, refAbstract=null), Reference(id=1329457171311473102, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=倪庆剑,彭文强,张志政,等. 基于信息增强传输的时空图神经网络交通流预测[J]. 计算机研究与发展,2022,59(2):282−293, articleTitle=null, refAbstract=null), Reference(id=1329457171382776271, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Ni Qingjian, Peng Wenqiang, Zhang Zhizheng, et al. Spatial-temporal graph neural network for traffic flow prediction based on information enhanced transmission[J]. Journal of Computer Research and Development, 2022, 59(2): 282−293 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329457171483439569, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821−7826, articleTitle=null, refAbstract=null), Reference(id=1329457171546354130, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Aggarwal C C. An Introduction to Social Network Data Analytics[M]. Berlin: Springer, 2011, articleTitle=null, refAbstract=null), Reference(id=1329457171642823123, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440−442, articleTitle=null, refAbstract=null), Reference(id=1329457171764457940, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167−256, articleTitle=null, refAbstract=null), Reference(id=1329457171844149718, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Newman M E J, Watts D J, Strogatz S H. Random graph models of social networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(suppl_1): 2566−2572, articleTitle=null, refAbstract=null), Reference(id=1329457171911258583, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Batagelj V, Zaveršnik M. Short cycle connectivity[J]. Discrete Mathematics, 2007, 307(3): 310−318, articleTitle=null, refAbstract=null), Reference(id=1329457171982561752, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Burt R S. Structural holes and good ideas[J]. American Journal of Sociology, 2004, 110(2): 349−399, articleTitle=null, refAbstract=null), Reference(id=1329457172045476313, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Foucault Welles B, Van Devender A, Contractor N. Is a Friend a Friend? Investigating the Structure of Friendship Networks in Virtual Worlds[M]//CHI’10 Extended Abstracts on Human Factors in Computing Systems. New York: ACM, 2010: 4027−4032, articleTitle=null, refAbstract=null), Reference(id=1329457172125168091, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang F, Gou XY, Zou L. Top-k heavy weight triangles listing on graph stream[J]. World Wide Web, 2023, 26(4): 1827−1851, articleTitle=null, refAbstract=null), Reference(id=1329457172200665564, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Z, Wilson C, Wang X, et al. Uncovering social network sybils in the wild[J]. ACM Transactions on Knowledge Discovery from Data, 2014, 8(1): 1−29, articleTitle=null, refAbstract=null), Reference(id=1329457172259385821, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Welser H T, Gleave E, Fisher D, et al. Visualizing the signatures of social roles in online discussion groups[J]. Journal of Social Structure, 2007, 8(2): 1−32, articleTitle=null, refAbstract=null), Reference(id=1329457172326494686, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Becchetti L, Boldi P, Castillo C, et al. Efficient semi-streaming algorithms for local triangle counting in massive graphs[C]//Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 16−24, articleTitle=null, refAbstract=null), Reference(id=1329457172389409247, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Becchetti L, Boldi P, Castillo C, et al. Efficient algorithms for large-scale local triangle counting[J]. ACM Transactions on Knowledge Discovery from Data, 2010, 4(3): 1−28, articleTitle=null, refAbstract=null), Reference(id=1329457172456518113, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Eckmann J P, Moses E. Curvature of co-links uncovers hidden thematic layers in the world wide web[J]. Proceedings of the National Academy of Sciences, 2002, 99(9): 5825−5829, articleTitle=null, refAbstract=null), Reference(id=1329457172540404194, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang N, Zhang JB, Tan K L, et al. On triangulation-based dense neighborhood graph discovery[J]. Proceedings of the VLDB Endowment, 2010, 4(2): 58−68, articleTitle=null, refAbstract=null), Reference(id=1329457172603318755, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Bar-Yossef Z, Kumar R, Sivakumar D. Reductions in streaming algorithms, with an application to counting triangles in graphs[C]//Proc of the 13th annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: SIAM, 2002: 623−632, articleTitle=null, refAbstract=null), Reference(id=1329457172678816229, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Tsourakakis C E, Drineas P, Michelakis E, et al. Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation[J]. Social Network Analysis and Mining, 2011, 1: 75−81, articleTitle=null, refAbstract=null), Reference(id=1329457172741730790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Epasto A, Lattanzi S, Mirrokni V, et al. Ego-Net community mining applied to friend suggestion[J]. Proceedings of the VLDB Endowment, 2015, 9(4): 324−335, articleTitle=null, refAbstract=null), Reference(id=1329457172804645351, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Lim Y, Jung M, Kang U. Memory-efficient and accurate sampling for counting local triangles in graph streams: From simple to multigraphs[J]. ACM Transactions on Knowledge Discovery from Data, 2018, 12(1): 1−28, articleTitle=null, refAbstract=null), Reference(id=1329457172875948520, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Latapy M. Main-memory triangle computations for very large (sparse (power-law)) graphs[J]. Theoretical Computer Science, 2008, 407(1): 458−473, articleTitle=null, refAbstract=null), Reference(id=1329457172951445994, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Itai A, Rodeh M. Finding a minimum circuit in a graph[C]//Proc of the 9th annual ACM Symposium on Theory of Computing. New York: ACM, 1977: 1−10, articleTitle=null, refAbstract=null), Reference(id=1329457173018554859, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Coppersmith D, Winograd S. Matrix multiplication via arithmetic progressions[C]//Proc of the 19th annual ACM Symposium on Theory of Computing. New York: ACM, 1987: 1−6, articleTitle=null, refAbstract=null), Reference(id=1329457173085663724, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Alon N, Yuster R, Zwick U. Finding and counting given length cycles[J]. Algorithmica, 1997, 17(3): 209−223, articleTitle=null, refAbstract=null), Reference(id=1329457173148578285, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Cohen J. Graph twiddling in a MapReduce world[J]. Computing in Science & Engineering, 2009, 11(4): 29−41, articleTitle=null, refAbstract=null), Reference(id=1329457173224075759, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Suri S, Vassilvitskii S. Counting triangles and the curse of the last reducer[C]//Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2011: 607−614, articleTitle=null, refAbstract=null), Reference(id=1329457173286990320, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Park H M, Chung C W. An efficient MapReduce algorithm for counting triangles in a very large graph[C]//Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 539−548, articleTitle=null, refAbstract=null), Reference(id=1329457173366682097, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Arifuzzaman S, Khan M, Marathe M. Patric: A parallel algorithm for counting triangles in massive networks[C]//Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 529−538, articleTitle=null, refAbstract=null), Reference(id=1329457173442179571, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Park H M, Silvestri F, Kang U, et al. MapReduce triangle enumeration with guarantees[C]//Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 1739−1748, articleTitle=null, refAbstract=null), Reference(id=1329457173530259956, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Park H M, Myaeng S H, Kang U. Pte: Enumerating trillion triangles on distributed systems[C]//Proc of the 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1115−1124, articleTitle=null, refAbstract=null), Reference(id=1329457173597368821, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Park H M, Silvestri F, Pagh R, et al. Enumerating trillion subgraphs on distributed systems[J]. ACM Transactions on Knowledge Discovery from Data, 2018, 12(6): 1−30, articleTitle=null, refAbstract=null), Reference(id=1329457173656089078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Tsourakakis C E, Kang U, Miller G L, et al. Doulion: Counting triangles in massive graphs with a coin[C]//Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 837−846, articleTitle=null, refAbstract=null), Reference(id=1329457173723197943, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Pagh R, Tsourakakis C E. Colorful triangle counting and a MapReduce implementation[J]. Information Processing Letters, 2012, 112(7): 277−281, articleTitle=null, refAbstract=null), Reference(id=1329457173794501112, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Ahmed N K, Duffield N, Neville J, et al. Graph sample and hold: A framework for big-graph analytics[C]//Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 1446−1455, articleTitle=null, refAbstract=null), Reference(id=1329457173865804281, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Lim Y, Kang U. MASCOT: Memory-efficient and accurate sampling for counting local triangles in graph streams[C]//Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 685−694, articleTitle=null, refAbstract=null), Reference(id=1329457173924524538, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Ahmed N K, Duffield N, Willke T, et al. On sampling from massive graph streams[J]. arXiv preprint arXiv: 1703.02625, 2017, articleTitle=null, refAbstract=null), Reference(id=1329457174008410620, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=40, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Shin K, Hammoud M, Lee E, et al. Tri-Fly: Distributed estimation of global and local triangle counts in graph streams[C]//Proc of Pacific-Asia Conf on Knowledge Discovery and Data Mining. Berlin: Springer, 2018: 651−663, articleTitle=null, refAbstract=null), Reference(id=1329457174067130877, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=41, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang PH, Jia P, Qi YY, et al. REPT: A streaming algorithm of approximating global and local triangle counts in parallel[C]//Proc of the 35th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2019: 758−769, articleTitle=null, refAbstract=null), Reference(id=1329457174117462526, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=42, rfOrder=42, authorNames=null, journalName=null, refType=null, unstructuredReference=Shin K, Lee E, Oh J, et al. CoCos: Fast and accurate distributed triangle counting in graph streams[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(3): 1−30, articleTitle=null, refAbstract=null), Reference(id=1329457174205542912, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=43, rfOrder=43, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang X, Song C, Yu MD, et al. Distributed triangle approximately counting algorithms in simple graph stream[J]. ACM Transactions on Knowledge Discovery from Data, 2022, 16(4): 1−43, articleTitle=null, refAbstract=null), Reference(id=1329457174264263169, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=44, rfOrder=44, authorNames=null, journalName=null, refType=null, unstructuredReference=Gou XY, Zou L. Sliding window-based approximate triangle counting with bounded memory usage[J]. The VLDB Journal, 2023, 32(5): 1087−1110, articleTitle=null, refAbstract=null), Reference(id=1329457174322983426, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=45, rfOrder=45, authorNames=null, journalName=null, refType=null, unstructuredReference=Jha M, Seshadhri C, Pinar A. A space efficient streaming algorithm for triangle counting using the birthday paradox[C]//Proc of the 19th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 589−597, articleTitle=null, refAbstract=null), Reference(id=1329457174385897987, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=46, rfOrder=46, authorNames=null, journalName=null, refType=null, unstructuredReference=Pavan A, Tangwongsan K, Tirthapura S, et al. Counting and sampling triangles from a graph stream[J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1870−1881, articleTitle=null, refAbstract=null), Reference(id=1329457174457201156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=47, rfOrder=47, authorNames=null, journalName=null, refType=null, unstructuredReference=Tangwongsan K, Pavan A, Tirthapura S. Parallel triangle counting in massive streaming graphs[C]//Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 781−786, articleTitle=null, refAbstract=null), Reference(id=1329457174528504325, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=48, rfOrder=48, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang LL, Jiang H, Wang F, et al. T-sample: A dual reservoir-based sampling method for characterizing large graph streams[C]//Proc of the 35th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2019: 1674−1677, articleTitle=null, refAbstract=null), Reference(id=1329457174599807495, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=49, rfOrder=49, authorNames=null, journalName=null, refType=null, unstructuredReference=Kutzkov K, Pagh R. Triangle counting in dynamic graph streams[C]//Proc of Scandinavian Workshop on Algorithm Theory. Berlin: Springer, 2014: 306−318, articleTitle=null, refAbstract=null), Reference(id=1329457174671110664, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=50, rfOrder=50, authorNames=null, journalName=null, refType=null, unstructuredReference=Bulteau L, Froese V, Kutzkov K, et al. Triangle counting in dynamic graph streams[J]. Algorithmica, 2016, 76(1): 259−278, articleTitle=null, refAbstract=null), Reference(id=1329457174734025225, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=51, rfOrder=51, authorNames=null, journalName=null, refType=null, unstructuredReference=Han G, Sethu H. Edge sample and discard: A new algorithm for counting triangles in large dynamic graphs[C]//Proc of the 2017 IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. New York: ACM, 2017: 44−49, articleTitle=null, refAbstract=null), Reference(id=1329457174817911306, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=52, rfOrder=52, authorNames=null, journalName=null, refType=null, unstructuredReference=Stefani L D, Epasto A, Riondato M, et al. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size[J]. ACM Transactions on Knowledge Discovery from Data, 2017, 11(4): 1−50, articleTitle=null, refAbstract=null), Reference(id=1329457174889214475, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=53, rfOrder=53, authorNames=null, journalName=null, refType=null, unstructuredReference=Shin K, Oh S, Kim J, et al. Fast, accurate and provable triangle counting in fully dynamic graph streams[J]. ACM Transactions on Knowledge Discovery from Data, 2020, 14(2): 1−39, articleTitle=null, refAbstract=null), Reference(id=1329457174973100556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=54, rfOrder=54, authorNames=null, journalName=null, refType=null, unstructuredReference=Lee D, Shin K, Faloutsos C. Temporal locality-aware sampling for accurate triangle counting in real graph streams[J]. The VLDB Journal, 2020, 29(6): 1501−1525, articleTitle=null, refAbstract=null), Reference(id=1329457175031820814, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=55, rfOrder=55, authorNames=null, journalName=null, refType=null, unstructuredReference=Yu CY, Liu HM, Wahab F, et al. Global triangle estimation based on first edge sampling in large graph streams[J]. The Journal of Supercomputing, 2023, 79(13): 14079−14116, articleTitle=null, refAbstract=null), Reference(id=1329457175107318287, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=56, rfOrder=56, authorNames=null, journalName=null, refType=null, unstructuredReference=Vitter J S. Random sampling with a reservoir[J]. ACM Transactions on Mathematical Software, 1985, 11(1): 37−57, articleTitle=null, refAbstract=null), Reference(id=1329457175187010064, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=57, rfOrder=57, authorNames=null, journalName=null, refType=null, unstructuredReference=Gemulla R, Lehner W, Haas P J. Maintaining bounded-size sample synopses of evolving datasets[J]. The VLDB Journal, 2008, 17: 173−201, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329457163828834674, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=1, ext=[AuthorCompanyExt(id=1329457163837223283, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107), AuthorCompanyExt(id=1329457163845611892, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163828834674, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
1人工智能与数字经济广东省实验室(深圳) 广东深圳 518107)]), AuthorCompany(id=1329457163904332149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, xref=2, ext=[AuthorCompanyExt(id=1329457163912720758, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060), AuthorCompanyExt(id=1329457163921109367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, companyId=1329457163904332149, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=
2深圳大学计算机与软件学院 广东深圳 518060)])], figs=[ArticleFig(id=1329457167452713378, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 1, caption=
The framework of EHADS algorithm, figureFileSmall=Qck9uIM1Hcb8Yz69D5punw==, figureFileBig=t47Aa3zGVExSj/x0HYp0TA==, tableContent=null), ArticleFig(id=1329457167515627939, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图1, caption=
EHADS算法框架, figureFileSmall=Qck9uIM1Hcb8Yz69D5punw==, figureFileBig=t47Aa3zGVExSj/x0HYp0TA==, tableContent=null), ArticleFig(id=1329457167670817188, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 2, caption=
Two different types of streaming graph, figureFileSmall=e6P7m6CYQA9q6Bn+drAv4Q==, figureFileBig=380UH7mqVnxYTv9XunfxnQ==, tableContent=null), ArticleFig(id=1329457167746314661, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图2, caption=
2种不同类型的流式图, figureFileSmall=e6P7m6CYQA9q6Bn+drAv4Q==, figureFileBig=380UH7mqVnxYTv9XunfxnQ==, tableContent=null), ArticleFig(id=1329457167809229223, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 3, caption=
Examples of global triangles and local triangles, figureFileSmall=/TFzpT14XzsRAz3gmc6q6A==, figureFileBig=VPBl2xIn1wj/4y2wn1I1/w==, tableContent=null), ArticleFig(id=1329457167880532392, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图3, caption=
全局三角形与局部三角形示例, figureFileSmall=/TFzpT14XzsRAz3gmc6q6A==, figureFileBig=VPBl2xIn1wj/4y2wn1I1/w==, tableContent=null), ArticleFig(id=1329457167951835561, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 4, caption=
Examples of changes in the number of triangles in dynamic graph, figureFileSmall=5cWA/50q/b8DIMAYGyr+7A==, figureFileBig=XACj7YemDb4P5rhRz3eYmw==, tableContent=null), ArticleFig(id=1329457168010555819, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图4, caption=
动态图中的三角形数量变化示例, figureFileSmall=5cWA/50q/b8DIMAYGyr+7A==, figureFileBig=XACj7YemDb4P5rhRz3eYmw==, tableContent=null), ArticleFig(id=1329457168073470380, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 5, caption=
Eight different types of triangle pair in dynamic graph stream, figureFileSmall=vC2UEmKGn9IuvERfUAPwtQ==, figureFileBig=M0N1PfVBWF5nAWgLqphsKA==, tableContent=null), ArticleFig(id=1329457168123802029, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图5, caption=
动态图流中8种不同类型的三角形对, figureFileSmall=vC2UEmKGn9IuvERfUAPwtQ==, figureFileBig=M0N1PfVBWF5nAWgLqphsKA==, tableContent=null), ArticleFig(id=1329457168182522286, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 6, caption=
The framework of EHADS-g algorithm, figureFileSmall=t8S2XzpHKF42LKjW3PtM6w==, figureFileBig=QLExuVfaYY+Oj45yNzGlKw==, tableContent=null), ArticleFig(id=1329457168245436847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图6, caption=
EHADS-g算法框架, figureFileSmall=t8S2XzpHKF42LKjW3PtM6w==, figureFileBig=QLExuVfaYY+Oj45yNzGlKw==, tableContent=null), ArticleFig(id=1329457168325128624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 7, caption=
Approximate probability density function of the estimators provided by different algorithms, figureFileSmall=yz2Em2rbIJU7c26iHuD64A==, figureFileBig=DMp6SfQZjXJIOuM4xbpgOA==, tableContent=null), ArticleFig(id=1329457168392237489, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图7, caption=
各算法提供的估计量的近似概率密度函数, figureFileSmall=yz2Em2rbIJU7c26iHuD64A==, figureFileBig=DMp6SfQZjXJIOuM4xbpgOA==, tableContent=null), ArticleFig(id=1329457168572592562, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 8, caption=
GAPE of distributed stream algorithms on different datasets, figureFileSmall=6PgS7rgT6i7eJN9tsGhC1w==, figureFileBig=2rhXgzLQOdusBYtfSbIL8Q==, tableContent=null), ArticleFig(id=1329457169784746420, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图8, caption=
分布式流算法在不同数据集上的GAPE, figureFileSmall=6PgS7rgT6i7eJN9tsGhC1w==, figureFileBig=2rhXgzLQOdusBYtfSbIL8Q==, tableContent=null), ArticleFig(id=1329457169860243893, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 9, caption=
RMSE of distributed stream algorithms on different datasets, figureFileSmall=ITZGOG6BgLCg4uGIhZDVHA==, figureFileBig=nSGS/HDOfGNVViSfomplrA==, tableContent=null), ArticleFig(id=1329457169918964150, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图9, caption=
分布式流算法在不同数据集上的RMSE, figureFileSmall=ITZGOG6BgLCg4uGIhZDVHA==, figureFileBig=nSGS/HDOfGNVViSfomplrA==, tableContent=null), ArticleFig(id=1329457169981878711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 10, caption=
GAPE of distributed stream algorithms on different datasets, figureFileSmall=9rBC0ZyIsbcaF9w8+sgnAw==, figureFileBig=SI7tS9VeEDsthPD+Gu1rfw==, tableContent=null), ArticleFig(id=1329457170069959096, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图10, caption=
分布式流算法在不同数据集上的GAPE, figureFileSmall=9rBC0ZyIsbcaF9w8+sgnAw==, figureFileBig=SI7tS9VeEDsthPD+Gu1rfw==, tableContent=null), ArticleFig(id=1329457170141262266, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 11, caption=
RMSE of distributed stream algorithms on different datasets, figureFileSmall=QR3BLUqp0dU9le8I7LxVIQ==, figureFileBig=f4DjQ1GZDdyolz018j56Sg==, tableContent=null), ArticleFig(id=1329457170195788219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图11, caption=
分布式流算法在不同数据集上的RMSE, figureFileSmall=QR3BLUqp0dU9le8I7LxVIQ==, figureFileBig=f4DjQ1GZDdyolz018j56Sg==, tableContent=null), ArticleFig(id=1329457170250314172, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 12, caption=
The runtime of distributed stream algorithms on different datasets, figureFileSmall=Pn9ZTDc018MpGICbt24lcQ==, figureFileBig=sXCdzCwubGsjz0X6gbhRew==, tableContent=null), ArticleFig(id=1329457170309034429, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图12, caption=
分布式流算法在不同数据集上的运行时间, figureFileSmall=Pn9ZTDc018MpGICbt24lcQ==, figureFileBig=sXCdzCwubGsjz0X6gbhRew==, tableContent=null), ArticleFig(id=1329457170367754686, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Figure 13, caption=
Scalability of EHADS on different datasets, figureFileSmall=pR31ONmay28jhRG56BnHeQ==, figureFileBig=oYKJ8BnKrlPG4cwtDqKPjA==, tableContent=null), ArticleFig(id=1329457170439057856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=图13, caption=
EHADS在不同数据集上的可扩展性, figureFileSmall=pR31ONmay28jhRG56BnHeQ==, figureFileBig=oYKJ8BnKrlPG4cwtDqKPjA==, tableContent=null), ArticleFig(id=1329457170518749633, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Table 1, caption=
Symbol Definitions Employed in Our Paper
, figureFileSmall=null, figureFileBig=null, tableContent=
| 符号 | 定义 |
|---|
| $\varPi $ | 动态图流(按时间输入的边操作序列) |
| ${e^t}$ | 时刻$t$到达的边操作 |
| ${\mathcal{G}^t} = ( {{\mathcal{V}^t},{\mathcal{E}^t}} )$ | 在时刻$t$的原始图 |
| $\mathcal{S}_i^t$ | 在时刻$t$第$i$个工作节点维护的样本集 |
| $\mathcal{N}_i^t[u]$ | 样本集$\mathcal{S}_i^t$中顶点$u$的邻居集合 |
| $\{ u,v\} $ | 顶点$u$和顶点$v$之间的边 |
| $\{ u,v,w\} $ | 由顶点$u,v,w$形成的三角形 |
| ${\mathcal{T}^t}$ | 图${\mathcal{G}^t}$中全部三角形的集合 |
| ${\mathcal{T}^t}[u]$ | 与顶点$u$相关的局部三角形集合 |
| $ \hat \tau $ | 图中全局三角形数量的估计值 |
| $ \hat \tau [u] $ | 图中与顶点$u$相关的局部三角形数量的估计值 |
| $m$ | 哈希函数的映射范围 |
| $p = 1/m$ | 边采样概率 |
| $h( \cdot )$ | EHADS算法的边哈希函数 |
| ${h_j}( \cdot )$ | 第$j$组工作节点的边哈希函数 |
| $ {\mathcal{A}^t} $ | 在时刻$t$之前图流中新增的所有三角形集合 |
| ${\mathcal{D}^t}$ | 在时刻$t$之前图流中被删除的所有三角形集合 |
| $\mathcal{M},\mathcal{W},\mathcal{C}$ | 主节点、工作节点、聚合节点的集合 |
), ArticleFig(id=1329457170585858498, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=表1, caption=
本文所采用的符号定义
, figureFileSmall=null, figureFileBig=null, tableContent=
| 符号 | 定义 |
|---|
| $\varPi $ | 动态图流(按时间输入的边操作序列) |
| ${e^t}$ | 时刻$t$到达的边操作 |
| ${\mathcal{G}^t} = ( {{\mathcal{V}^t},{\mathcal{E}^t}} )$ | 在时刻$t$的原始图 |
| $\mathcal{S}_i^t$ | 在时刻$t$第$i$个工作节点维护的样本集 |
| $\mathcal{N}_i^t[u]$ | 样本集$\mathcal{S}_i^t$中顶点$u$的邻居集合 |
| $\{ u,v\} $ | 顶点$u$和顶点$v$之间的边 |
| $\{ u,v,w\} $ | 由顶点$u,v,w$形成的三角形 |
| ${\mathcal{T}^t}$ | 图${\mathcal{G}^t}$中全部三角形的集合 |
| ${\mathcal{T}^t}[u]$ | 与顶点$u$相关的局部三角形集合 |
| $ \hat \tau $ | 图中全局三角形数量的估计值 |
| $ \hat \tau [u] $ | 图中与顶点$u$相关的局部三角形数量的估计值 |
| $m$ | 哈希函数的映射范围 |
| $p = 1/m$ | 边采样概率 |
| $h( \cdot )$ | EHADS算法的边哈希函数 |
| ${h_j}( \cdot )$ | 第$j$组工作节点的边哈希函数 |
| $ {\mathcal{A}^t} $ | 在时刻$t$之前图流中新增的所有三角形集合 |
| ${\mathcal{D}^t}$ | 在时刻$t$之前图流中被删除的所有三角形集合 |
| $\mathcal{M},\mathcal{W},\mathcal{C}$ | 主节点、工作节点、聚合节点的集合 |
), ArticleFig(id=1329457170657161667, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Table 2, caption=
Time Complexity and Space Complexity of EHADS Algorithm for Processing the First t Edges in Graph Stream
, figureFileSmall=null, figureFileBig=null, tableContent=
| 节点类型 | 时间复杂度 | 空间复杂度 |
|---|
| 主节点 | $O(t |\mathcal{W}|)$ | $O(1)$ |
| 工作节点 | $ O( {{t^2}/m} ) $ | $ O\left( {t/m} \right) $ |
| 聚合节点 | $ O\left(\dfrac{{{t^2}\left| \mathcal{W} \right|}}{m}\right) $ | $O( {| {{\mathcal{V}^t}} |} )$ |
), ArticleFig(id=1329457170711687621, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=表2, caption=
EHADS算法处理图流中前$t$条边的时间复杂度和空间复杂度
, figureFileSmall=null, figureFileBig=null, tableContent=
| 节点类型 | 时间复杂度 | 空间复杂度 |
|---|
| 主节点 | $O(t |\mathcal{W}|)$ | $O(1)$ |
| 工作节点 | $ O( {{t^2}/m} ) $ | $ O\left( {t/m} \right) $ |
| 聚合节点 | $ O\left(\dfrac{{{t^2}\left| \mathcal{W} \right|}}{m}\right) $ | $O( {| {{\mathcal{V}^t}} |} )$ |
), ArticleFig(id=1329457170799768006, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Table 3, caption=
Real-World Graph Datasets Used in the Experiments
, figureFileSmall=null, figureFileBig=null, tableContent=
| 数据集 | 顶点数 | 边数 | 三角形数 | 描述 |
|---|
| Email-Enron | 36 692 | 183 831 | 727 044 | 电子邮件通信网络 |
| HepPh | 12 008 | 118 521 | 3 358 499 | 合著者网络 |
| AstroPh | 18 772 | 198 110 | 1 351 441 | 合著者网络 |
| Gowalla | 196 591 | 950 327 | 2 273 138 | 在线社交网络 |
| DBLP | 317 080 | 1 049 866 | 2 224 385 | 合著者网络 |
| NotreDame | 325 729 | 1 090 108 | 8 910 005 | 网页超链接网络 |
), ArticleFig(id=1329457170875265479, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=表3, caption=
实验中所用真实世界图数据集
, figureFileSmall=null, figureFileBig=null, tableContent=
| 数据集 | 顶点数 | 边数 | 三角形数 | 描述 |
|---|
| Email-Enron | 36 692 | 183 831 | 727 044 | 电子邮件通信网络 |
| HepPh | 12 008 | 118 521 | 3 358 499 | 合著者网络 |
| AstroPh | 18 772 | 198 110 | 1 351 441 | 合著者网络 |
| Gowalla | 196 591 | 950 327 | 2 273 138 | 在线社交网络 |
| DBLP | 317 080 | 1 049 866 | 2 224 385 | 合著者网络 |
| NotreDame | 325 729 | 1 090 108 | 8 910 005 | 网页超链接网络 |
), ArticleFig(id=1329457170942374344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=EN, label=Table 4, caption=
Runtime of Distributed Stream Algorithms with 99% Estimation Accuracy s
, figureFileSmall=null, figureFileBig=null, tableContent=
| 方法 | Email- Enron | HepPh | AstroPh | Gowalla | DBLP | NotreDame |
|---|
| RFESFD-Parallel | 22.59 | 16.93 | 17.84 | 683.57 | 44.55 | 370.94 |
| TriestFD-Parallel | 20.89 | 21.24 | 22.65 | 531.18 | 55.26 | 238.02 |
| ThinkDfast-Parallel | 14.07 | 14.32 | 9.54 | 45.57 | 41.19 | 47.80 |
| ThinkDacc-Parallel | 16.24 | 11.53 | 13.97 | 131.76 | 46.78 | 96.43 |
| WRSDel-Parallel | 25.40 | 28.95 | 27.88 | 143.05 | 69.19 | 808.84 |
| EHADS | 12.99 | 9.03 | 7.09 | 39.30 | 33.46 | 39.14 |
), ArticleFig(id=1329457171009483209, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329457158091026749, language=CN, label=表4, caption=
估计精度为99%时分布式流算法的运行时间
, figureFileSmall=null, figureFileBig=null, tableContent=
| 方法 | Email- Enron | HepPh | AstroPh | Gowalla | DBLP | NotreDame |
|---|
| RFESFD-Parallel | 22.59 | 16.93 | 17.84 | 683.57 | 44.55 | 370.94 |
| TriestFD-Parallel | 20.89 | 21.24 | 22.65 | 531.18 | 55.26 | 238.02 |
| ThinkDfast-Parallel | 14.07 | 14.32 | 9.54 | 45.57 | 41.19 | 47.80 |
| ThinkDacc-Parallel | 16.24 | 11.53 | 13.97 | 131.76 | 46.78 | 96.43 |
| WRSDel-Parallel | 25.40 | 28.95 | 27.88 | 143.05 | 69.19 | 808.84 |
| EHADS | 12.99 | 9.03 | 7.09 | 39.30 | 33.46 | 39.14 |
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202440120, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440120, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202440120, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202440120, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1722441600000, fullTextJson=null, articleText=null, reference=null)