Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream

Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream Zhuo Li, YuXuan Zhao, Jindian Liu, Yu Zhang, Kaihua Liu This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6241870/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 15 Oct, 2025 Read the published version in World Wide Web → Version 1 posted 9 You are reading this latest preprint version Abstract Graph streams of sequentially arriving edges are commonly used to represent complex structured data in interactive networks. Typically, graph streams are extremely large and high-velocity. Existing schemes by using graph sketch for summarizing graph stream have demonstrated significant success in handling both storage and query tasks. However, the performance degradation caused by non-uniformly distributions of edge weight and node degree remains unresolved. Current schemes only consider one type of non-uniformly distributions. Meanwhile, there are many periodic edges appearing within the graph streams and finding such periodic edges is crucial for network applications. However, there are no established measurements that predominantly focus on finding periodic edge. To this end, a general graph sketch framework called PMatrix is proposed. PMatrix not only can detect periodic edges, but also adapts to the non-uniformly distributions of edge weight and node degree simultaneously. The performance of PMatrix is evaluated on both CPU and OVS platforms. The experimental results show that PMatrix achieves substantial improvements in measurement precision, reducing the ARE by 62.29% to 99.82% compared with the state-of-the-art graph sketches. For periodic edge measurement, PMatrix has low ARE and F1-Score reaches 100%. Graph sketch Graph stream Graph summarization Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 15 Oct, 2025 Read the published version in World Wide Web → Version 1 posted Editorial decision: Revision requested 30 Apr, 2025 Reviews received at journal 30 Apr, 2025 Reviews received at journal 20 Apr, 2025 Reviewers agreed at journal 30 Mar, 2025 Reviewers agreed at journal 26 Mar, 2025 Reviewers invited by journal 24 Mar, 2025 Editor assigned by journal 19 Mar, 2025 Submission checks completed at journal 19 Mar, 2025 First submitted to journal 17 Mar, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6241870","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":433317046,"identity":"fd9d1a4e-5f3f-46db-8851-9cc1ab11f356","order_by":0,"name":"Zhuo Li","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAp0lEQVRIiWNgGAWjYDACdsbGBww8IFYCsVqYGZsNDpCohYFN4gADKVrkm5nbqj/IHGbgZ88xYPi5gwgtjM2MbTcO8BxmkOx5Y8DYe4YYdzFDtRjcyDEAsonQwgZUVgDSYk+0Fh6QMrAtEsRqkQAGssQZnnQeiTPPCg72EqNFvr394YfKHms5/vbkjQ9+EqMFDBh7IPF/gFgNQPCDBLWjYBSMglEw8gAAgKMvpt5FvsIAAAAASUVORK5CYII=","orcid":"","institution":"Tianjin University","correspondingAuthor":true,"prefix":"","firstName":"Zhuo","middleName":"","lastName":"Li","suffix":""},{"id":433317047,"identity":"76c735a7-cc55-430c-ac0b-c48040942fd7","order_by":1,"name":"YuXuan Zhao","email":"","orcid":"","institution":"Tianjin University","correspondingAuthor":false,"prefix":"","firstName":"YuXuan","middleName":"","lastName":"Zhao","suffix":""},{"id":433317048,"identity":"3ab8a5b5-4af5-46be-85f3-c81ce706565e","order_by":2,"name":"Jindian Liu","email":"","orcid":"","institution":"Tianjin University","correspondingAuthor":false,"prefix":"","firstName":"Jindian","middleName":"","lastName":"Liu","suffix":""},{"id":433317049,"identity":"69eecffd-f951-4c04-88c3-190a69c97d28","order_by":3,"name":"Yu Zhang","email":"","orcid":"","institution":"Peng Cheng Laboratory","correspondingAuthor":false,"prefix":"","firstName":"Yu","middleName":"","lastName":"Zhang","suffix":""},{"id":433317050,"identity":"db9cd9cd-b533-486a-abfd-184fd5c039d5","order_by":4,"name":"Kaihua Liu","email":"","orcid":"","institution":"Tianjin University","correspondingAuthor":false,"prefix":"","firstName":"Kaihua","middleName":"","lastName":"Liu","suffix":""}],"badges":[],"createdAt":"2025-03-17 07:08:32","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6241870/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6241870/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11280-025-01378-4","type":"published","date":"2025-10-15T15:57:08+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":93955925,"identity":"089ed710-8cef-4f87-b494-89cc937a008b","added_by":"auto","created_at":"2025-10-20 16:07:08","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":3502257,"visible":true,"origin":"","legend":"","description":"","filename":"TowardAccurateWeightbasedMeasurementandPeriodicEdgeMeasurementinGraphStream.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6241870/v1_covered_1658562e-eda8-454e-b5a0-912c3edbd285.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"world-wide-web","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"wwwj","sideBox":"Learn more about [World Wide Web](http://link.springer.com/journal/11280)","snPcode":"11280","submissionUrl":"https://submission.nature.com/new-submission/11280/3","title":"World Wide Web","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Graph sketch, Graph stream, Graph summarization","lastPublishedDoi":"10.21203/rs.3.rs-6241870/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6241870/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eGraph streams of sequentially arriving edges are commonly used to represent complex structured data in interactive networks. Typically, graph streams are extremely large and high-velocity. Existing schemes by using graph sketch for summarizing graph stream have demonstrated significant success in handling both storage and query tasks. However, the performance degradation caused by non-uniformly distributions of edge weight and node degree remains unresolved. Current schemes only consider one type of non-uniformly distributions. Meanwhile, there are many periodic edges appearing within the graph streams and finding such periodic edges is crucial for network applications. However, there are no established measurements that predominantly focus on finding periodic edge. To this end, a general graph sketch framework called PMatrix is proposed. PMatrix not only can detect periodic edges, but also adapts to the non-uniformly distributions of edge weight and node degree simultaneously. The performance of PMatrix is evaluated on both CPU and OVS platforms. The experimental results show that PMatrix achieves substantial improvements in measurement precision, reducing the ARE by 62.29% to 99.82% compared with the state-of-the-art graph sketches. For periodic edge measurement, PMatrix has low ARE and F1-Score reaches 100%.\u003c/p\u003e","manuscriptTitle":"Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-03-25 09:53:29","doi":"10.21203/rs.3.rs-6241870/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-04-30T07:44:26+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-04-30T05:11:31+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-04-21T03:44:48+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"212179451901759446739158828015239336937","date":"2025-03-30T20:30:03+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"130603817286757599031506616310082731813","date":"2025-03-26T06:22:33+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-03-24T07:26:46+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-03-19T12:00:32+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-03-19T11:57:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"World Wide Web","date":"2025-03-17T07:00:21+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"world-wide-web","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"wwwj","sideBox":"Learn more about [World Wide Web](http://link.springer.com/journal/11280)","snPcode":"11280","submissionUrl":"https://submission.nature.com/new-submission/11280/3","title":"World Wide Web","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"003e358c-2e6e-4501-a649-d05e55604fe3","owner":[],"postedDate":"March 25th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-10-20T15:59:53+00:00","versionOfRecord":{"articleIdentity":"rs-6241870","link":"https://doi.org/10.1007/s11280-025-01378-4","journal":{"identity":"world-wide-web","isVorOnly":false,"title":"World Wide Web"},"publishedOn":"2025-10-15 15:57:08","publishedOnDateReadable":"October 15th, 2025"},"versionCreatedAt":"2025-03-25 09:53:29","video":"","vorDoi":"10.1007/s11280-025-01378-4","vorDoiUrl":"https://doi.org/10.1007/s11280-025-01378-4","workflowStages":[]},"version":"v1","identity":"rs-6241870","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6241870","identity":"rs-6241870","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}