時序圖

時序圖中包括如下元素：角色，對象，生命線，控制焦點和消息。

1、角色（Actor）

系統角色，可以是人或者其他系統，子系統。

2、對象(Object)

對象代表時序圖中的對象在交互中所扮演的角色，位於時序圖頂部和對象代表

類角色。

對象一般包含以下三種命名方式：

第一種方式包含對象名和類名。

第二種方式只顯示類名不顯示對象名，即為一個匿名對象。

第三種方式只顯示對象名不顯示類名。

3、生命線(Lifeline)

生命線代表時序圖中的對象在一段時期內的存在。時序圖中每個對象和底部中心都有一條垂直的虛線，這就是對象的生命線，對象間 的消息存在於兩條虛線間。

4、控制焦點(Activation)

控制焦點代表時序圖中的對象執行一項操作的時期，在時序圖中每條生命線上的窄的矩形代表活動期。它可以被理解成C語言語義中一對花括弧“{}”中的內容。

5、消息(Message)

消息是定義交互和協作中交換信息的類，用於對實體間的通信內容建模，信息用於在實體間傳遞信息。允許實體請求其他的服務，類角色通過發送和接受信息進行通信。

時序圖描述對象是如何交互的，並且將重點放在消息序列上。也就是說，描述消息是如何在對象間發送和接收的。時序圖有兩個坐標軸：縱坐標軸顯示時間，橫坐標軸顯示對象。每一個對象的表示方法是：矩形框中寫有對象和 / 或類名，且名字下面有下劃線；同時有一條縱向的虛線表示對象在序列中的執行情況(即發送和接收的消息對象的活動) ，這條虛線稱為對象的生命線。對象間的通信用對象的生命線之間的水平的消息線來表示，消息線的箭頭說明消息的類型，如同步，非同步或簡單。瀏覽時序圖的方法是，從上到下查看對象間交換的消息，分析那些隨著時間的流逝而發生的消息交換。

時序圖中的消息可以是信號、操作調用或類似於C++ 中的RPC（ Remote Procedure Call,遠程過程調用）或Java中的RMI（ Remote Method Invocation ，遠程方法調用）。當對象接收到一個消息時，該對象中的一項活動就會啟動，我們把這一過程稱做激活（ Activation ）。激活會顯示控制焦點，表明對象在某一個時間點開始執行。一個被激活的對象或者是執行它自身的代碼，或者是等待另一個對象的返回（該被激活的對象已經向另一個對象發送了消息）。在圖形上，激活被繪製為對象生命線上的一個瘦高矩形。

消息可以用消息名及參數來標識。消息還可帶有條件表達式，表示分支或決定是否發送消息。如果用於表示分支，則每個分支是相互排斥的，即在某一時刻僅可發送分支中的一個消息。消息也可以有順序號，但是在時序圖中，消息的順序號很少使用，因為時序圖已經將消息的順序顯式地表示出來了。

一個對象可以通過發送消息來創建另一個對象，當一個對象被刪除或自我刪除時，該對象用 "X"標識。

1、確定交互過程的上下文；

2、識別參與過程的交互對象；

3、為每個對象設置生命線；

4、從初始消息開始，依次畫出隨後消息；

5、考慮消息的嵌套，標示消息發生時的時間點，則採用FOC（focus of control）；

6、說明時間約束的地點。

時序圖影響力最大化問題，即在時序圖上尋找K個頂點使得信息最大化的傳播。傳播模型的選擇和節點間傳播概率的計算是影響力最大化問題的基礎，由於基於靜態圖的IC(Independent Cascade model)傳播模型無法應用於時圖，因此首先對 IC 模型進行改進提出了ICT(Independent Cascade model on Temporal Graph)傳播模型，使信息可以通過ICT傳播模型在時序圖上進行傳播。而後通過改進PageRank演演算法來進行計算節點間的傳播概率。然後在此基礎上將時序圖影響力最大化問題分為兩步來進行實現。

通過對基於靜態圖的影響力最大化演演算法的研究並改進，從而將影響力最大化問題的研究對象由靜態圖轉移到動態圖上去，並提出了可以解決動態圖影響力最大化問題的演演算法。

首次在動態圖上進行了影響力最大化問題的研究。其中對SKIM 演演算法進行改進將其適用於動態圖的影響力最大化問題的實現。其採用反向可達採樣方法首先採樣處多個採樣集合，通過採樣集合來找出種子節點集合，而後圖中會有節點的添加或刪除操作，通過計算節點的刪除或添加對當前採樣集合的影響來重新計算種子節點集合。由於其完全沒有考慮節點間聯繫的因素，且是以全局的角度來研究時序圖影響力最大化問題，其間並無節點增刪的操作，所以研究方法無法解決所研究的問題。則是使用的一種新的窗口滑動的模型來研究動態圖上的實時影響力最大化問題，其研究思路為設置一個時間窗口w，將節點間的聯繫看作一個action，並將這些 action 按照時間的先後順序存放在w中。窗口w會隨著時間向下滑動，此時便涉及到新的action的進入和舊的action的退出(因為窗口的大小是可以人為設定的)，根據節點的進入和退出，來判斷是否需要對在上一個時間段所求出的窗口中的種子節點進行重新計算。而由於是從全局的角度在時序圖上研究影響力最大化問題，所以研究思路也無法解決所要研究的問題。

時序圖

時序圖和靜態圖的本質上的不同是時序圖在邊的權重上加入了時間戳這一因素。靜態圖上的邊一旦存在便不會因時間的變化而改變，而在時序圖中，邊會因時間的變化在兩種狀態下相互轉化：激活狀態和非激活狀態。時序圖中頂點間只在邊處在激活狀態下時是存在聯繫的。

在現實生活中有很多常見的網路都可以描述為時序圖。(1)點對點通信網路：如電子郵件、手機簡訊等。(2)一對多的消息傳播網路：在這種網路中注重的是單一用戶對其餘多個用戶的信息傳播。(3)生物信息網路：如代謝網路、蛋白質互作用網路等。研究表明，在生物信息網路中，各節點間的交流是時間相關的，所以Teresa M. Przytycka等人認為對於生物信息網路的分析是需要藉助於動態網路來實現的，且在對蛋白質互作用和基因調控網路的研究工作中已經有研究者開始分析時間對網路的影響。

基本的時序圖影響力最大化演演算法的思想是：將時序圖影響力問題分為兩步解決，首先第一步計算節點影響力，然後第二步是根據第一步所得出的實驗結果使用貪心演演算法逐次尋找出邊際效應最大的那個節點作為種子節點，直到找出k個種子節點為止。

首先提出了時序圖節點影響力計算演演算法SIC演演算法以及其改進演演算法ISIC演演算法，然後在此基礎上計算節點的邊際效應，並由此提出基本的可以解決時序圖影響力最大化問題的基本演演算法BIMT演演算法。

為每位病人構建一個醫療時序圖，時序圍的表示形式壓縮了原始數據使其更緊湊，從而有效解決了醫療數據的稀疏性問題，並且為每位病人的分散數據提供了一種全景概括視圖。

疾病風陰預測方法MTPGraph中病人時序圖將每位病人原始EHRs數據中的時序臨床事件轉變為時序圖，為所有病人提供了一種一致性表示形式，並考慮了不同臨床事件之間的時序關係。在形成圖的過程中，將用藥進行了粗粒度劃分，例如，'地高辛（Digoxin）'和萬爽力（Vasorel）'可歸類為’抗心絞痛藥物（AntianginalAgents）'。畫像圖的節點表示粗粒度醫療事件（即，疾病名稱，粗粒度用藥，化驗名稱等）；根據臨床事件的時間戳來形成有向邊，可以捕捉任意兩個醫療事件之間的時序關係；邊權重反映出相鄰兩個醫療事件之間的平均時間間隔，邊越粗權重越大，則平均時間間隔越短，這種表示形式簡便直觀，易於捕捉到不同臨床事件之間時序關係的強弱。

從疾病風陰預測方法MTPGraph中可為各種分析任務捕捉到綜合全面的信息。在構建時序圖時，與文獻不同的是需要根據實際的數據格式進行以下幾方面考慮：首先需要從病人電子健康檔案記錄中抽取臨床事件，根據中國藥典（ChinesePharmacopoeia）將其劃分為粗粒度醫療事件，基於相對應的時間戳形成時序序列，最後將得到的粗粒度事件序列轉變成時序圖。基於圖的表示方式能夠用更簡潔的方式捕捉到隱藏在事件序列中的時序關係，並且在時序序列中擁有一致順序重複出現的事件對在時序圖中只出現一次，意味著這種表示形式能夠幫助抵制稀疏性及不規則觀察。

疾病風陰預測方法MTPGraph中疾病風險預測提出了一種挖掘頻繁時序特徵圖的演演算法。為了執行不同疾病風險預測任務，例如預測冠私病患者的病情是否好控制，或者預測慢性阻塞性肺病患者在未來90天內是否會再次住院等任務，都需要採取以下步驟：首先要構建信息量豐富的特徵圖，利用提出的頻繁時序子序列挖掘演演算法TRApriori，Apriori是最成熟的頻繁項集挖掘演演算法之一，基於該方法去獲得頻繁時序子序列，隨後形成頻繁時序特徵圖；其次如疾病風陰預測方法MTPGraph中疾病風險預測所示基於病人時序圖及頻繁時序特徵圖來構建特徵向量，每個病人時序圖都可由第一步得到的特徵圖重新組成，隨之產生一個重構係數，即生成的是特徵向量，用來進行有效的疾病風險預測。通過對慢性阻塞性肺病（ChronicObstructiveP*ulmonaryDisease，COPD）群體及冠心病（CoronaryHeartDisease，CHD）群體發病風險的早期預測來驗證所提方法的有效性。