時序圖
?時序圖是一種UML交互圖及序列圖，通過描述對象之間發(fā)送消息的時間順序顯示多個對象之間的動態(tài)協(xié)作。它可以表示用例的行為順序，當(dāng)執(zhí)行一個用例行為時，其中的每條消息對應(yīng)一個類操作或狀態(tài)機中引起轉(zhuǎn)換的觸發(fā)事件。
組成元素
時序圖中包括如下元素：角色，對象，生命線，控制焦點和消息。
1、角色（Actor）
系統(tǒng)角色，可以是人或者其他系統(tǒng)，子系統(tǒng)。
2、對象(Object)
對象代表時序圖中的對象在交互中所扮演的角色，位于時序圖頂部和對象代表
對象一般包含以下三種命名方式：
第一種方式包含對象名和類名。
第二種方式只顯示類名不顯示對象名，即為一個匿名對象。
第三種方式只顯示對象名不顯示類名。
3、生命線(Lifeline)
4、控制焦點(Activation)
控制焦點代表時序圖中的對象執(zhí)行一項操作的時期，在時序圖中每條生命線上的窄的矩形代表活動期。它可以被理解成C語言語義中一對花括號“{}”中的內(nèi)容。
消息是定義交互和協(xié)作中交換信息的類，用于對實體間的通信內(nèi)容建模，信息用于在實體間傳遞信息。允許實體請求其他的服務(wù)，類角色通過發(fā)送和接受信息進行通信。
結(jié)構(gòu)
時序圖描述對象是如何交互的，并且將重點放在消息序列上。也就是說，描述消息是如何在對象間發(fā)送和接收的。時序圖有兩個坐標軸：縱坐標軸顯示時間，橫坐標軸顯示對象。每一個對象的表示方法是：矩形框中寫有對象和 / 或類名，且名字下面有下劃線；同時有一條縱向的虛線表示對象在序列中的執(zhí)行情況(即發(fā)送和接收的消息對象的活動) ，這條虛線稱為對象的生命線。對象間的通信用對象的生命線之間的水平的消息線來表示，消息線的箭頭說明消息的類型，如同步，異步或簡單。瀏覽時序圖的方法是，從上到下查看對象間交換的消息，分析那些隨著時間的流逝而發(fā)生的消息交換。
時序圖中的消息可以是信號、操作調(diào)用或類似于C++ 中的RPC（ Remote Procedure Call,遠程過程調(diào)用）或Java中的RMI（ Remote Method Invocation ，遠程方法調(diào)用）。當(dāng)對象接收到一個消息時，該對象中的一項活動就會啟動，我們把這一過程稱做激活（ Activation ）。激活會顯示控制焦點，表明對象在某一個時間點開始執(zhí)行。一個被激活的對象或者是執(zhí)行它自身的代碼，或者是等待另一個對象的返回（該被激活的對象已經(jīng)向另一個對象發(fā)送了消息）。在圖形上，激活被繪制為對象生命線上的一個瘦高矩形。
消息可以用消息名及參數(shù)來標識。消息還可帶有條件表達式，表示分支或決定是否發(fā)送消息。如果用于表示分支，則每個分支是相互排斥的，即在某一時刻僅可發(fā)送分支中的一個消息。消息也可以有順序號，但是在時序圖中，消息的順序號很少使用，因為時序圖已經(jīng)將消息的順序顯式地表示出來了。
一個對象可以通過發(fā)送消息來創(chuàng)建另一個對象，當(dāng)一個對象被刪除或自我刪除時，該對象用 "X"標識。
創(chuàng)建步驟
1、確定交互過程的上下文；
2、識別參與過程的交互對象；
3、為每個對象設(shè)置生命線；
4、從初始消息開始，依次畫出隨后消息；
5、考慮消息的嵌套，標示消息發(fā)生時的時間點，則采用FOC（focus of control）；
6、說明時間約束的地點。
影響算法
時序圖影響力最大化問題，即在時序圖上尋找K個頂點使得信息最大化的傳播。傳播模型的選擇和節(jié)點間傳播概率的計算是影響力最大化問題的基礎(chǔ)，由于基于靜態(tài)圖的IC(Independent Cascade model)傳播模型無法應(yīng)用于時圖，因此首先對 IC 模型進行改進提出了ICT(Independent Cascade model on Temporal Graph)傳播模型，使信息可以通過ICT傳播模型在時序圖上進行傳播。而后通過改進PageRank算法來進行計算節(jié)點間的傳播概率。然后在此基礎(chǔ)上將時序圖影響力最大化問題分為兩步來進行實現(xiàn)。
動態(tài)圖最大化算法
通過對基于靜態(tài)圖的影響力最大化算法的研究并改進，從而將影響力最大化問題的研究對象由靜態(tài)圖轉(zhuǎn)移到動態(tài)圖上去，并提出了可以解決動態(tài)圖影響力最大化問題的算法。
首次在動態(tài)圖上進行了影響力最大化問題的研究。其中對SKIM 算法進行改進將其適用于動態(tài)圖的影響力最大化問題的實現(xiàn)。其采用反向可達采樣方法首先采樣處多個采樣集合，通過采樣集合來找出種子節(jié)點集合，而后圖中會有節(jié)點的添加或刪除操作，通過計算節(jié)點的刪除或添加對當(dāng)前采樣集合的影響來重新計算種子節(jié)點集合。由于其完全沒有考慮節(jié)點間聯(lián)系的因素，且是以全局的角度來研究時序圖影響力最大化問題，其間并無節(jié)點增刪的操作，所以研究方法無法解決所研究的問題。則是使用的一種新的窗口滑動的模型來研究動態(tài)圖上的實時影響力最大化問題，其研究思路為設(shè)置一個時間窗口w，將節(jié)點間的聯(lián)系看作一個action，并將這些 action 按照時間的先后順序存放在w中。窗口w會隨著時間向下滑動，此時便涉及到新的action的進入和舊的action的退出(因為窗口的大小是可以人為設(shè)定的)，根據(jù)節(jié)點的進入和退出，來判斷是否需要對在上一個時間段所求出的窗口中的種子節(jié)點進行重新計算。而由于是從全局的角度在時序圖上研究影響力最大化問題，所以研究思路也無法解決所要研究的問題。
時序圖
時序圖和靜態(tài)圖的本質(zhì)上的不同是時序圖在邊的權(quán)重上加入了時間戳這一因素。靜態(tài)圖上的邊一旦存在便不會因時間的變化而改變，而在時序圖中，邊會因時間的變化在兩種狀態(tài)下相互轉(zhuǎn)化：激活狀態(tài)和非激活狀態(tài)。時序圖中頂點間只在邊處在激活狀態(tài)下時是存在聯(lián)系的。
在現(xiàn)實生活中有很多常見的網(wǎng)絡(luò)都可以描述為時序圖。(1)點對點通信網(wǎng)絡(luò)：如電子郵件、手機短信等。(2)一對多的消息傳播網(wǎng)絡(luò)：在這種網(wǎng)絡(luò)中注重的是單一用戶對其余多個用戶的信息傳播。(3)生物信息網(wǎng)絡(luò)：如代謝網(wǎng)絡(luò)、蛋白質(zhì)互作用網(wǎng)絡(luò)等。研究表明，在生物信息網(wǎng)絡(luò)中，各節(jié)點間的交流是時間相關(guān)的，所以Teresa M. Przytycka等人認為對于生物信息網(wǎng)絡(luò)的分析是需要借助于動態(tài)網(wǎng)絡(luò)來實現(xiàn)的，且在對蛋白質(zhì)互作用和基因調(diào)控網(wǎng)絡(luò)的研究工作中已經(jīng)有研究者開始分析時間對網(wǎng)絡(luò)的影響。
時序圖影響力最大化基本算法
基本的時序圖影響力最大化算法的思想是：將時序圖影響力問題分為兩步解決，首先第一步計算節(jié)點影響力，然后第二步是根據(jù)第一步所得出的實驗結(jié)果使用貪心算法逐次尋找出邊際效應(yīng)最大的那個節(jié)點作為種子節(jié)點，直到找出k個種子節(jié)點為止。
首先提出了時序圖節(jié)點影響力計算算法SIC算法以及其改進算法ISIC算法，然后在此基礎(chǔ)上計算節(jié)點的邊際效應(yīng)，并由此提出基本的可以解決時序圖影響力最大化問題的基本算法BIMT算法。
風(fēng)險預(yù)測
為每位病人構(gòu)建一個醫(yī)療時序圖，時序圍的表示形式壓縮了原始數(shù)據(jù)使其更緊湊，從而有效解決了醫(yī)療數(shù)據(jù)的稀疏性問題，并且為每位病人的分散數(shù)據(jù)提供了一種全景概括視圖
病人時序圖
疾病風(fēng)陰預(yù)測方法MTPGraph中病人時序圖將每位病人原始EHRs數(shù)據(jù)中的時序臨床事件轉(zhuǎn)變?yōu)闀r序圖，為所有病人提供了一種一致性表示形式，并考慮了不同臨床事件之間的時序關(guān)系。在形成圖的過程中，將用藥進行了粗粒度劃分，例如，'地高辛（Digoxin）'和萬爽力（Vasorel）'可歸類為’抗心絞痛藥物（AntianginalAgents）'。畫像圖的節(jié)點表示粗粒度醫(yī)療事件（即，疾病名稱，粗粒度用藥，化驗名稱等）；根據(jù)臨床事件的時間戳來形成有向邊，可以捕捉任意兩個醫(yī)療事件之間的時序關(guān)系；邊權(quán)重反映出相鄰兩個醫(yī)療事件之間的平均時間間隔，邊越粗權(quán)重越大，則平均時間間隔越短，這種表示形式簡便直觀，易于捕捉到不同臨床事件之間時序關(guān)系的強弱。
從疾病風(fēng)陰預(yù)測方法MTPGraph中可為各種分析任務(wù)捕捉到綜合全面的信息。在構(gòu)建時序圖時，與文獻不同的是需要根據(jù)實際的數(shù)據(jù)格式進行以下幾方面考慮：首先需要從病人電子健康檔案記錄中抽取臨床事件，根據(jù)中國藥典（ChinesePharmacopoeia）將其劃分為粗粒度醫(yī)療事件，基于相對應(yīng)的時間戳形成時序序列，最后將得到的粗粒度事件序列轉(zhuǎn)變成時序圖。基于圖的表示方式能夠用更簡潔的方式捕捉到隱藏在事件序列中的時序關(guān)系，并且在時序序列中擁有一致順序重復(fù)出現(xiàn)的事件對在時序圖中只出現(xiàn)一次，意味著這種表示形式能夠幫助抵制稀疏性及不規(guī)則觀察。
疾病風(fēng)險預(yù)測
疾病風(fēng)陰預(yù)測方法MTPGraph中疾病風(fēng)險預(yù)測提出了一種挖掘頻繁時序特征圖的算法。為了執(zhí)行不同疾病風(fēng)險預(yù)測任務(wù)，例如預(yù)測冠私病患者的病情是否好控制，或者預(yù)測慢性阻塞性肺病患者在未來90天內(nèi)是否會再次住院等任務(wù)，都需要采取以下步驟：首先要構(gòu)建信息量豐富的特征圖，利用提出的頻繁時序子序列挖掘算法TRApriori，Apriori是最成熟的頻繁項集挖掘算法之一，基于該方法去獲得頻繁時序子序列，隨后形成頻繁時序特征圖；其次如疾病風(fēng)陰預(yù)測方法MTPGraph中疾病風(fēng)險預(yù)測所示基于病人時序圖及頻繁時序特征圖來構(gòu)建特征向量，每個病人時序圖都可由第一步得到的特征圖重新組成，隨之產(chǎn)生一個重構(gòu)系數(shù)，即生成的是特征向量，用來進行有效的疾病風(fēng)險預(yù)測。