第五章 時序圖網絡建模

2021-02-13 數聯未來

第五章 時序圖網絡建模

5.1 時序圖數據定義


5.1.1 時序圖定義

在數時序圖之前，我們先來看看靜態圖結構。靜態圖結構，其結構是靜態的，節點和邊的屬性、數量等都不會隨時間改變，這個一般僅供圖論中研究。其具體的數學定義如下： G = {V, E}，其中V表示定點集合，E 表示連邊集合，網絡的拓撲結構可以用鄰接矩陣 D = {Dij}n×n表示，若每個節點具有自己的維屬性向量，則網絡的屬性矩陣表示為A={Aij}n×n，靜態圖網絡整體便可表示為G={V,E,A}。

與之對應的就是時序圖網絡了，簡單來說，時序圖網絡就是指圖網絡結構隨時間不斷變化、演化的動態網絡，網絡中節點和邊的屬性、數量等隨時間改變。按理來說，世界上所有事物都可以構成一個拓撲圖，這個拓撲圖就是動態網絡，最常見的就是我們的社交網絡，每天都有新的人員加入、離去，或修改人員屬性，這個巨大的社交網絡就是時序圖網絡。下面我們給出其具體的數學定義：給定一個時序圖G=(V,E),其中V是G中的一組頂點，E是G的一組邊，對於一條邊e∈E，用四元組（u,v,t,r）來表示，其中頂點u,v∈V，t是起始時間，r是從u到v遍歷時間，則從u到v的終止時間為t+r,邊e的起始時間為t(e),遍歷時間為r(e),即e在[t,t+r]時是被激活的。


如圖所示，圖（a）表示有4個頂點的靜態圖；圖（b）表示存在與1-10時間閾值內的時序圖，圖（c）表示圖（b）中頂點和邊對應的時間序列。

 

5.1.2 時序圖分類

時序圖網絡可以分成兩種情況，一種是，頂點間的相互作用是在一個確切時間上發生的、持續時間可以忽略不計的時序圖，即r(e)=0。直接一點說就是該種時序圖網絡不考慮兩個節點之間相互作用持續的時間，而是只考慮某個時刻是否有相互作用；另外一種是，時序圖中的邊在時間閾值中被激活，即r(e)≠0。常用來表示持續時間很重要的時序圖，例如在交通網絡中，頂點間的邊表示通行時間。

5.1.3 時序圖性質

由於時序圖網絡中最重要的屬性是時間，所以時間對時序圖網絡有重要影響，這也導致了其性質不同於我們常見的靜態結構。比如說連通性，時序圖的網絡結構在不斷變化，兩個節點在某個時刻可能存在一條連接路徑，某些時刻可能又不存在一條連接路徑，所以時序圖網絡的連通性是基於時間的，其也可以分為強聯通和弱連通：

還有其它的一些性質也有些不同，比如：

頂點之間的距離：指兩個頂點可達的最短時間；

時序圖直徑：最小的頂點距離；

5.2 時序圖數據模型

要對時序圖網絡進行分析，必須首先對時序圖網絡進行數據模型建模，其常見的數據模型主要有三種，下面分別進行介紹。

5.2.1 連續時間圖模型

連續時間圖模型就是邊構建帶有時間信息標籤的圖結構，一條邊有一個或多個時間戳。對時序上的網絡等間隔取快照是比較粗糙的方法，不能捕捉所取間隔時間內網絡的變化。更加細緻的表示方法是記錄網絡中所有變化：定義一個動態網絡

 

，其中VT是所有定點的集合，

 

記錄了定點出現的時間。

 

表示網絡中的時序連邊(temporal edges)，也就是將每個連邊都打上多個時間戳，表示連邊在該時刻發生變化。每一條邊都被賦予了一個特定的時間戳

 

另外，t屬於R+還可以定義網絡的屬性矩陣，AT記錄每個點的屬性在不同時刻的值。

 

這種模型的特點是，可以構建統一的查詢機制，但時間信息複雜，為時序圖構建索引也相對複雜並且索引量巨大，索引效果一般。

5.2.2 時間圖快照模型

時間圖快照模型是指在離散的時間上為時序圖構建相應的快照。這類表示方法在時序上對動態網絡等間隔取快照(Snapshot)，從而得到網絡演化的離散序列，定義為：


其中


表示動態網絡在 t 時刻的快照。這種表示方法相當於將動態網絡拆解成單個靜態網絡的序列。

 

該種模型的特點是，適用於具有特定時間結構的時序圖，特別是在即時網絡中；這種情況下，時序圖是由一系列靜態圖組成的，該建模方式與動態圖類似，只能滿足離散時間上的查詢與挖掘需求，而且保存所有快照需要大量的內存空間，因此也不能很好的應用與所有的時序圖。

5.2.3 頂點多副本模型

頂點多副本模型是指通過時間為頂點構建副本，將時序圖完全轉換成靜態圖，即在同一時刻的圖中同時存在頂點和頂點的多個副本，通過頂點副本將時序圖轉換成靜態圖。該種數據模型的特點是隨著數據的增多，圖的規模不斷增大，稠密且大規模的圖數據不斷增多，這種方法使圖的規模激增，因此不能很好的應用於大圖數據中。

5.3 時序圖應用及方向

並不是說所有的時空網絡都可以用時序圖的方法來解決，一般來說，只有當一個網絡有時序性結構，符合時序圖的框架，並且涉及到時間標度時才需要用時序圖來解決問題。而且如果動態系統的變換速度遠快於動態連結的速度，或者圖中的邊是活躍的變化的，那麼就不需要將動態系統轉換成時序圖。針對目前時序圖的研究來看，主要是沿著如下的幾個方法：

提高查詢處理與挖掘效率；

更多的查詢處理與挖掘方法；

構建統一的時序圖管理系統；

5.4 基於時序圖的時間序列分析

前面章節討論過，時間序列數據可以通過引入數據節點之間的關係來構建時序圖網絡，以實現模型中對數據節點之間的相互影響的建模，進一步加強模型的預測精度。從上述三種時序圖數據模型分析可知，可用於時間序列分析的主要是基於時間圖快照的數據模型，該模型符合時間序列等間距的特點，可以方便的建立每個時刻的圖數據結構。如下圖所示：

 

每個時刻都可以構建成一個靜態圖，每個靜態圖都具有一定的全局屬性、節點屬性、邊屬性，而這些屬性都是隨時間不斷演變的，其中可能存在某些演變的規律和模式。後續，我們將進一步研究如何利用圖神經網絡算法來分析時序圖的演變，包括全圖屬性、邊屬性、節點屬性隨時間的演變規律。

參考文獻：

大規模時序圖數據的查詢處理與挖掘技術綜述.王一舒、袁野等.計算機研究與發展 55(9)：1889-1902 2018

未來地圖：物聯--數聯--智聯

【物聯】

【數聯】

【智聯】

相關焦點

  • 靜態時序分析聖經翻譯計劃9——第五章:延遲計算 (上)
    5.1 概述5.1.1 延遲計算基礎典型的設計中包括各種組合邏輯單元和時序邏輯單元，我們使用如圖5-1中所示的邏輯設計來描述延遲計算的概念：圖5-1庫中為每個單元的每個輸入引腳都指定了電容值，因此，設計中的每個網絡都具有容性負載，該負載是該網絡每個扇出的引腳負載電容再加上互連線的寄生電容之和。
  • 收藏系列-UML建模之時序圖(Sequence Diagram)
    一、時序圖簡介（Brief introduction）       二、時序圖元素（Sequence Diagram Elements
  • 實例介紹UML時序圖用法
    基於UML時序圖的網絡視頻監控系統UML是UnifiedModelingLanguage的簡稱，是00P(Object-Orientedprogramming面向對象編程)技術及至所成，可用於確定、展示和記錄軟體系統，是一種便於軟體系統規約化、可視化的構造及建模標識。而其中的圖形標記，尤其適用與面向對象的軟體設計。
  • 靜態時序分析聖經翻譯計劃10——第五章:延遲計算 (下)
    這種公共點稱為壓擺合併點（slew merge point）。選擇哪個壓擺在壓擺合併點處繼續向下傳播呢？考慮圖5-10所示的2輸入單元：圖5-10由於引腳A上的信號改變，引腳Z上的壓擺到達較早，但上升緩慢（壓擺較小）；由於引腳B上的信號改變，引腳Z上的壓擺到達較晚，但上升很快（壓擺較大）。在壓擺合併點（例如引腳Z），應選擇哪個壓擺進一步傳播呢？
  • 時序圖和類圖的關係
    什麼是時序圖 　　時序圖（Sequence Diagram），又名序列圖、循序圖、順序圖，是一種UML交互圖。類圖是面向對象建模的主要組成部分。它既用於應用程式的系統分類的一般概念建模，也用於詳細建模，將模型轉換成編程代碼。類圖也可用於數據建模。 　　時序圖和類圖的關係
  • 快速學習時序圖:時序圖簡介、畫法及實例
    時序圖作為常用的UML交互圖，可以直觀的傳達系統內外之間的交互過程，經常用在詳細設計文檔中。下面本文綜合參考了多篇時序圖的教程，根據作者的思路將時序圖做了更深入的講解。一、 什麼是時序圖？時序圖（Sequence Diagram），亦稱為序列圖、循序圖或順序圖，是一種UML交互圖。它通過描述對象之間發送消息的時間順序顯示多個對象之間的動態協作。時序圖是一個二維圖，橫軸表示對象，縱軸表示時間，消息在各對象之間橫向傳遞，依照時間順序縱向排列。
  • 解析UML時序圖的四大元素
    解析UML時序圖的四大元素 本文向大家介紹一下UML時序圖，UML時序圖描述對象是如何交互的，並且將重點放在消息序列上。也就是說，描述消息是如何在對象間發送和接收的。
  • 圖神經網絡前沿綜述:動態圖網絡
    導語 圖神經網絡已經被廣泛的應用於圖結構數據的建模和表徵學習，但是主流的研究都局限於處理靜態網絡數據，而真實的複雜網絡大多會隨時間發生結構和性質的演化
  • UML建模中的9種圖
    其中在第一步與第二步中所建立的模型都是靜態的，包括用例圖、類圖、對象圖、組件圖和部署圖等5種圖形，是標準建模語言UML的靜態建模機制。其中第三步中所建立的模型或者可以執行，或者表示執行時的時序狀態或交互關係。它包括狀態圖、活動圖、時序圖和協作圖等4種圖形，是標準建模語言UML的動態建模機制。
  • 看懂UML類圖和時序圖
    一起學習、成長、溫情的熱愛生活圖丨pexels這裡不會將UML的各種元素都提到，我只想講講類圖中各個類之間的關係；能看懂類圖中各個類之間的線條、箭頭代表什麼意思後，也就足夠應對日常的工作和交流；同時，我們應該能將類圖所表達的含義和最終的代碼對應起來
  • 時序圖中的實線和虛線分別表示什麼意思
    什麼是時序圖 　　時序圖（Sequence Diagram），又名序列圖、循序圖、順序圖，是一種UML交互圖。 　　2、對象（Object） 　　對象代表時序圖中的對象在交互中所扮演的角色，位於時序圖頂部和對象代表。對象實例類角色。 　　對象一般包含以下三種命名方式： 　　第一種方式包含對象名和類名。 　　第二種方式只顯示類名不顯示對象名，即為一個匿名對象。
  • 騰訊優圖實驗室高級研究員棟豪:時序動作分析技術的研究與應用 |...
    「騰訊優圖專場」，是智東西公開課邀請騰訊優圖實驗室面向開發者和科研人員，專注講解騰訊優圖實驗室前沿研究成果的系列線上公開課，第一階段共計三講。第一講由優圖實驗室資深高級研究員瑋劍主講，主題為《3D人臉重建技術的研究與應用實例》。第二講由優圖實驗室研究員太平主講，主題為《人臉安全技術的研究與應用》。
  • plc時序圖怎麼畫_plc時序圖編程方法
    打開APP plc時序圖怎麼畫_plc時序圖編程方法 發表於 2017-10-23 09:39:25 　　時序圖是描述設備工作過程的時間次序圖，也是用於直觀分析設備工作過程的一種圖形。
  • AAAI 2020 | 時序轉化為圖用於可解釋可推理的異常檢測
    近年來，可解釋的時序建模多著眼於離散時序，在時間軸上將時序分段，然後從分段中抓出可以用於判斷異常的表示，常見的方法有：字典方法[3]，找時序分段的特徵值形狀方法[4]，找時序分段的特殊波形基於以上背景為出發，為了描述時間序列的動態信息，同時提供可解釋的模型表示用於異常檢測，該論文嘗試將Shapelet映射回時序中, 探尋位置的敏感度，並隨時間累積轉移關係，構建Graph進行表示，形成一種可推理可解釋的方法用於時序建模與異常分析
  • 軟考備考之UML九種建模圖
    UML九種建模圖：用例圖、類圖、對象圖、順序圖、協作圖、狀態圖、活動圖、組件圖、配置圖。又可以靜動分為靜態視圖和動態視圖。靜態圖分為：用例圖，類圖，對象圖，包圖，構件圖，部署圖。動態圖分為：狀態圖，活動圖，協作圖，序列圖。
  • 時序圖、活動圖、狀態圖、協作圖的區別
    時序圖時序圖用於描述對象之間的傳遞消息的時間順序, 即用例中的行為順序.當執行一個用例時, 時序圖中的每條消息對應了一個類操作或者引起轉換的觸發事件.在 UML 中, 時序圖表示為一個二維的關係圖, 其中, 縱軸是時間軸, 時間延豎線向下延伸. 橫軸代表在協作中各個獨立的對象. 當對象存在時, 生命線用一條虛線表示, 消息用從一個對象的生命線到另一個對象的生命線的箭頭表示. 箭頭以時間的順序在圖中上下排列.
  • 【第三章:標準單元庫 下】靜態時序分析聖經翻譯計劃
    圖3-11對於如圖3-11所示的例子，可以將時序弧分為以下幾類：輸入到輸出的組合邏輯弧：這對應於直接從輸入到輸出的組合邏輯路徑，例如從輸入埠FIN到輸出埠FOUT。輸入時序邏輯弧：這對應於連接到觸發器D引腳的輸入埠的建立時間或保持時間。通常，在將模塊的輸入埠連接到觸發器的D引腳之前，可以存在一些組合邏輯。
  • 如何看懂時序圖(經典)
    以下是LCD1602的時序圖：　　大家要慢慢學會看時序圖，要知道操作一個器件的精華便蘊藏在其中，看懂看準了時序，你操控這個晶片就是非常容易的事了。1602的時序是我見過的一個最簡單的時序：　　　　2、上圖框出並註明了看懂此圖的一些常識：　　(1).時序圖最左邊一般是某一根引腳的標識，表示此行圖線體現該引腳的變化，上圖分別標明了RS、R/W、E、DB0~DB7四類引腳的時序變化。　　(2).有線交叉狀的部分，表示電平在變化，如上所標註。
  • 圖神經網絡入門(五)不同類型的圖
    （一）GCN 圖卷積網絡圖神經網絡入門（二）GRN 圖循環網絡圖神經網絡入門（三）GAT 圖注意力網絡圖神經網絡入門（四）GRN圖殘差網絡在此前介紹的所有工作基本上都圍繞無向的有了元路徑，我們就可以根據節點的邊類型和距離將鄰居節點分類，如此就可以將異構圖分解為一個同構圖的集合（這也被稱為多通道網絡）。
  • 乾貨|時間序列預測類問題下的建模方案探索實踐
    使用XGBoost模型處理時間序列預測類問題，需要將其轉換成回歸問題再進行構建，其具體建模流程如下圖所示。圖7 XGBoost模型建模流程圖使用機器學習類的模型進行時間序列預測，不需要進行平穩性檢驗，直接對訓練數據進行相關預處理即可，包括查重、查缺、清洗錯誤等。