自動社交網絡圖挖掘和可視化的製作方法

2023-11-07 22:26:47 2

專利名稱：自動社交網絡圖挖掘和可視化的製作方法
自動社交網絡圖挖掘和可視化許多社交網絡應用近年來在網際網路上上線，以允許人們在社交上以及職業上連接。通常，這樣的社交網絡應用要求用戶創建用戶標識(ID)和口令並標識其朋友以便創建簡檔。然而，全球資訊網或網際網路上的諸如新聞站點、博客、評論等許多網頁描述人們和其他實體的社交活動，儘管這些信息沒有列在社交網絡應用站點上。另外，儘管存在許多社交網絡應用，但沒有多少方式來容易地確定和查看人們和其他實體之間的社交連接或關係。概述提供本概述是為了以簡化的形式介紹將在以下詳細描述中進一步描述的一些概念。本概述並不旨在標識出所要求保護的主題的關鍵特徵或必要特徵，也不旨在用於限定所要求保護的主題的範圍。

此處描述的自動社交網絡圖挖掘和可視化技術從一般(不必是社交應用專用的)網頁挖掘社交連接，並允許對社交網絡關係進行可視化。更具體而言，在一個實施例中，該自動社交網絡圖挖掘和可視化技術對實體的社交網絡圖進行自動挖掘和布局。實體可以是例如人、組織或甚至關鍵詞。該技術使用一個或多個網頁上一實體的名稱和相關實體的名稱之間的距離來確定各實體之間的連接以及這些連接的強度。在挖掘過程中，輸入是一般的網頁。人或其他實體的名稱以及他們之間的社交連接被自動提取和綜合。對於每一實體名稱，其社交網絡圖被定義為在一個或多個網頁中連接到該實體名稱的名稱集和從該Web中標識的這些連接的實體名稱之間的社交連接集的結合。這些社交連接可由關係排序過程來加權。在一個實施例中，該社交網絡圖挖掘和可視化技術可使用一布局過程來生成圍繞人或其他實體的名稱的二維(2-D)社交網絡圖。在該技術的一個實施例中，該布局通過使用力指向模型和能量縮減過程來自動生成。在該布局中，社交連接權重由其兩個端點之間的距離來表示。該距離越短，則該連接權重越大。同樣，在一個實施例中，該布局過程聚集彼此緊密連接在一起的人或其他實體的名稱。


參考以下描述、所附權利要求書以及附圖，將更好地理解本公開的具體特徵、方面和優點，附圖中圖I是用於採用此處描述的自動社交網絡圖挖掘和可視化技術的一個示例性實施例的示例性體系結構。圖2描繪了用於採用自動社交網絡圖挖掘和可視化技術的示例性過程的流程圖。圖3描繪了用於根據自動社交網絡圖挖掘和可視化技術的一個示例性實施例來創建社交網絡圖的示例性過程的流程圖。圖4描繪了由自動社交網絡圖挖掘和可視化技術的一個示例性實施例創建的示例性社交網絡圖。
圖5描繪了在自動社交網絡圖挖掘和可視化技術的一個示例性實施例中採用的圖形用戶界面。圖6是可用於實現自動社交網絡圖挖掘和可視化技術的示例性計算設備的示意圖。詳細描述在對自動社交網絡圖挖掘和可視化技術的以下描述中，對附圖作出參考，附圖形成了該描述的一部分，且作為可實現此處所述的自動社交網絡圖挖掘和可視化技術的說明性示例示出。可以理解，可以利用其它實施例，並且可以作出結構上的改變而不背離所要求保護的主題的範圍。1. O自動社奪網絡圖校掘和可視化摶術以下各節提供了自動社交網絡圖挖掘和可視化技術的綜述，以及用於採用該技術的示例性體系結構、過程和用戶界面。1. 1摶術綜沭社交網絡近來受到了更多的關注。如Facebook和Twitter這樣的社交網絡應用和服務允許用戶增長其自己的私人社交網絡。然而，網際網路實際上包含了隱含於一般網頁中的文本中的公共社交網絡。例如，描述社交活動的網頁提供了這些網頁上所提到的人或實體之間的隱含社交連接。這些公共的隱含社交連接可被視為巨大的社交網絡圖。幾乎沒有進行任何工作來從並非為社交網絡應用特別設計的網頁中自動標識並呈現人和其他實體之間的社交連接。在一個實施例中，該自動社交網絡圖挖掘和可視化技術從一般的網頁中自動標識社交網絡連接，並以2-D布局提供允許查看者容易地標識該圖中的人或實體之間的連接以及這些連接的強度的社交網絡圖。在一個實施例中，該技術創建2-D可視化布局，該布局提供了特定實體的社交網絡圖為一組基於該實體和其他實體之間的連接和連接強度以徑向布局排列的頂點(名稱)和邊(社交連接)。該社交圖的所有者(例如，為其生成該圖的實體)被置於中心。採用上述挖掘過程和布局過程，來自web的社交網絡圖被自動生成並可視化。1. 2示例件體系結構圖1提供了用於採用自動社交網絡圖挖掘和可視化技術的一個實施例的示例性體系結構100。如圖I所示，體系結構100採用社交網絡圖挖掘和可視化模塊102，該模塊駐留在將參考圖6更詳細討論的計算設備600上。社交網絡圖挖掘和可視化模塊102用於挖掘社交網絡圖104並在顯示器106上將其呈現給用戶，用戶108可經由用戶界面110來操縱該社交網絡圖。網頁112被輸入到社交網絡圖挖掘和可視化模塊102中。網頁視覺解析器114將來自所輸入的每一網頁的網頁內容解析成信息塊116。信息塊116被輸入到名稱提取器118中，後者從信息塊中識別實體名稱。這些實體可以是例如人、組織或關鍵詞。標記了實體名稱的信息塊120被輸入到社交連接排序器122中，後者確定所標記的信息塊116中所標識的實體之間的一個或多個連接並對這些連接排序。社交連接排序器122還標識連接的強度並對其分配權重。用於確定排序的一個示例性過程將在下文中更詳細討論。社交連接排序器122輸出已排序的實體名稱及其連接權重124。這些連接權重124被輸入到社交連接綜合器126中，後者綜合所有已排序的實體名稱及其連接權重124，並使用力指向模型創建社交網絡圖104並在顯示器106上輸出該圖。一旦在顯示器106上顯示了社交網絡圖104的各部分，用戶108就能經由用戶界面110操縱該社交網絡圖104來示出其其他部分，這將在下文中更詳細討論。I. 3.自動社交網絡圖挖掘和可視化技術所採用的示例性過程以下各段提供了對用於採用自動社交網絡圖挖掘和可視 化技術的示例性過程的描述。應當理解，在某些情況下，動作的次序可以互換，並且在某些情況下，部分動作甚至可被省略。I. 3. I自動社奪網絡圖校掘用於採用自動社交網絡圖挖掘和可視化技術的一個實施例的過程的高級流程圖在圖2中示出。該技術的該實施例從一般的網頁中挖掘社交連接及其強度。如圖2所示，在框202，將這些網頁輸入到該過程中。這些輸入的網頁可例如通過web爬行器爬行網際網路來找到。每一所輸入的網頁的內容被解析成信息塊，如框204所示。例如，標識文本塊或其他鄰接數據塊的視覺解析器可用於解析網頁的內容。可使用各種常規技術來標識並解析該文本或其他鄰接數據塊。然後標識在信息塊中找到的人或實體的名稱，如框206所示。例如，這可由常規的名稱尋找器來完成。此處，常規名稱尋找器指的是能夠從信息塊中自動尋找實體名稱的任何計算機算法。如框208所示，然後對信息塊中的實體名稱之間的社交連接排序。在該技術的一個實施例中，排序考慮了名稱的位置以及信息塊中的環繞文本(例如，名稱的位置以及文本中將名稱隔開的特定距離或單詞數)。兩個名稱彼此越靠近，則認為連接的強度越強。關於該技術的一個實施例所採用的排序過程的細節將在下文中給出。然後對來自所有信息塊的已排序的社交連接進行綜合以確定在網頁上找到的實體之間的社交連接的強度，如框210所示。在社交網絡圖挖掘和可視化技術的一個實施例中，該綜合在確定對每一信息塊找到的連接的強度時，除了信息塊中的名稱的接近度之外，還考慮了在網頁上找到同一名稱集的頻率。社交連接的強度然後可用於各種目的，如確定某人的朋友是誰，或用於對這些社交連接繪圖以提供確定人或其他實體之間的社交連接強度的視覺幫助，如框212所示。I. 3. 2可視化社交連接圖3提供了由自動社交網絡圖挖掘和可視化技術用來可視化社交連接的一個示例性過程300的流程圖。在該技術的該實施例中，從一般的網頁中提取的人/實體的名稱之間的社交連接以2-D圖的形式來表示，該2-D圖具有一組表示名稱的頂點，以及一組表示社交連接的邊。使用力指向模型來表示該2-D圖，並且使用能量最小化過程來充分優化或增強該2-D圖的布局。如框302所示，輸入已排序社交連接的列表。將社交圖的所有者(為其顯示該圖的人)置於該2D圖的中心作為中心頂點，如框304所示。表示人或其他實體的名稱、且具有到社交圖的所有者的社交連接的頂點被置於中心頂點周圍的不同軌道中(或基於排序置於該中心頂點周圍的軌道中)，如框306所示。軌道的半徑越短，則該軌道中的頂點與中心頂點之間的社交連接越強。為每一社交連接創建中心頂點周圍的一條軌道，其中具有到該所有者的最強社交連接的頂點(實體)最接近該中心頂點。如框308所示，頂點然後可根據頂點之間的連通性被聚集到不同聚類中(例如，根據他們之間的連接以及將在下文中更詳細描述的能量最小化過程來聚集)。同一聚類中的頂點(例如，其之間具有多於一個連接的頂點)被彼此接近地放置。頂點聚類也被放置成使得頂點聚類不彼此重疊，如框310所示。如框312所示，然後使用力指向模型來充分優化2D圖的布局的均一性。圖4提供了由該技術的一個實施例產生的2D圖布局400的一個示例。在社交網絡圖挖掘和可視化技術的該實施例中，力指向模型通過採用一組力和能量最小化過程將該布局充分優化為均一I)每兩個頂點之間的排斥力402 (其一個示例在圖4中示出)；2)沿著邊的吸引力404 (例如，在頂點402之間的社交連接之間)；3)相鄰軌道之間的排斥力406 ；以及
4)被建模以隔離彼此之間沒有連接的聚類的不可穿透邊界408。5)圖中的每一對象，例如每一頂點、邊、軌道和不可穿透邊界，或者是徑向/切向自由的，或者兩個方向都是自由的，從而能夠根據力指向模型的力來移動。因此，在每一頂點處在力指向模型中有四種不同的力沿著邊的吸引力404 A(O) = < ;每兩個頂點之間的排斥力402ZW J)=古;相鄰軌道之間的排斥力4061肌) ^ ;以及
Uk'k -1
—_c^ g τ T不可穿透邊界$n ) = r 6U α ,,> .
4 5+ca9Wm'其中i，j表示第i個頂點和第j個頂點；d表示距離；0k表示第k條軌道；Um表示第m條不可穿透邊界；(^,2,3表示常量；Θ表示線的正交角，其穿過頂點和中心頂點以及不可穿透邊界；並且τ表示常量閾值。給定以上定義，一個頂點處的聚集力為
hmm= Σ fiihj)+TJ1HJ)+/AOk^1)+Yj4(i,um)
VMiJieaJWm當力在一個頂點處平衡時，該頂點處的聚集力為零。因此，該技術尋求最小化所有頂點的聚集力的總和。布局算法然後尋找頂點的適當放置，其中
放置=arg min Y FjΣ 可被認為是該布局的能量，因此該布局算法實際上縮減力模型的總能量。在
i
該技術的一個實施例中，能量縮減過程以迭代的方式來執行。在每一次迭代中，每一頂點沿著聚集力的方向移動。該過程在能量收斂於特定水平時停止。更具體而言，當能量下降時，頂點的總位移也減小。該技術設置一常量閾值。當總位移小於該值時，迭代過程停止。在那時之前，頂點在每一次迭代中保持移動，即，其位置改變。I. 3. 3對社奪連梓棑序
如先前所討論的，社交網絡圖挖掘和可視化技術的某些實施例採用了排序過程來對實體之間的社交連接排序。下節給出了關於在該技術的一個實施例中使用的排序過程的附加信息。該技術的一個實施例所採用的排序可描述如下。給定實體名稱列表Χ={Χ(ι，Χι，. . . }和網頁列表W= {wQ, W1, ... },每一網頁具有信息塊B= {bQ, b1； . . . },如果Xi, χ」出現在一個信息塊中，則信息塊中這兩個名稱之間的關係權重被定義為Rb (xi； Xj) =Rd · Rc其中Rd表示關係的距離度量，而R。表示關係的上下文度量。這兩個度量的定義如下
d(x^x.) — l
Rd (Xi, X) ) 二 I--^-)Rc= (Xi, Xj) =1. OK (Xi, Xj) = ΦTlkmK(Xi^Xj) = [kj
A此處，(Kxi, Xj)表示信息塊中Xi, Xj之間的字符距離。如果Xi, Xj不一起出現在信息塊中，則d(Xi，Xj)是無窮的。S卩，Rd等於零。變量K(Xi，Xj)表示在該信息塊中的兩個名稱之間發現的關係關鍵詞集，如「妻子」、「朋友」等。變量km表示預定義關鍵詞權重，km>1.0。在一個實施例中，每一關係關鍵詞具有預定義權重，例如，「妻子」具有權重2.0，「朋友」具有權重1.6。K(Xi7Xj)是對應於兩個名稱的關係關鍵詞的權重集。如果對於\和\沒有關係關鍵詞，則K(Xi，\)是空集，由「φ」表示。否則，K(Xi，\)將具有一個或多個值，如{I. 6，2.0，...}。在一個實施例中，關鍵詞集是手動收集的。當來自該集合的關鍵詞存在於具有兩個實體名稱的信息塊中時，使用一過程來決定是否使用該關鍵詞來描述這兩個實體名稱之間的關係。因而，Xi, Xj的全局關係權重被定義為，xJ) = Σ Σ Ux丨,xj)
W B該排序過程因而可計算信息塊中的所有實體之間的關係權重，並且可相應地對實體及其相關聯的關係權重排序。然而，應當注意，可使用其他排序過程來創建已排序的社交連接列表。注意，社交圖被定義為G=(V，E)，其中V是頂點集而E是邊集。從web中發現的每一獨特實體/人的名稱是圖中的頂點，即，V= Ixtl, Xl，. . . }。在具有非零權重的每一 Xi，Xj對之間，定義邊eijt)因而，E= IeijK其中R(Xi，Xj)>0。I. 4示例件用戶界面圖5示出了用於根據自動社交網絡圖挖掘和可視化技術的一個實施例來顯示和操縱社交圖的一個示例性用戶界面500。在該實施例中，用戶可通過在搜索框502中輸入名稱(例如，本例中的「C」)來搜索實體名稱(例如，人、組織或關鍵詞)。實體名稱(例如，C)被示為中心頂點504，並且其他連接的實體被示為圍繞中心頂點504的頂點506。頂點506之間的社交連接強度被示為邊508。兩個頂點506之間的邊508越短，則由連接的頂點所表示的實體之間的關係越強。兩個頂點506之間的邊508越長，則由連接的頂點所表示的實體之間的關係越弱。在一個實施例中，頂點506的顏色以及可任選的其後的背景以類似彩虹的顏色序列從0°到360°變化(例如，紅色510，橙色512，黃色514，綠色516，藍色518以及紫色520)。另外，節點或頂點506越接近，則節點的顏色(以及可任選的節點後的背景)越相似。在一個實施例中，節點/頂點顏色根據從0°到360°的極坐標改變。在一個實施例中，示例性用戶界面500還提供動畫。例如，當用戶用用戶輸入設備點擊(例如，選擇)一個頂點506時，整個社交圖/地圖522改變為以所點擊(例如，選擇)的頂點為中心的新地圖。在該切換轉移期間，有三種動畫a)將不在新地圖上的最初顯示的頂點不再顯示。b)將仍在新地圖中的最初顯示的頂點將移至新位置；以及c)曾不在原始地圖中的新頂點將出現並移至位置。用戶界面500還可包括光標控制524，以允許用戶在地圖522上移動以便顯示該圖的其他部分。用戶還可選擇各個頂點506來找出關於他們的附加信息。例如，在一個實施例中，如果用戶用滑鼠或其他輸入設備選擇一頂點，則將顯示具有關於與所選頂點相關聯 的實體的附加信息的彈出窗口或顯示屏幕。2. O計算環塏自動社交網絡圖挖掘和可視化技術被設計成在計算環境中操作。以下描述旨在提供其中可實現自動社交網絡圖挖掘和可視化技術的合適計算環境的簡明、概要描述。該技術可用各種通用或專用計算系統環境或配置來操作。可能合適的公知的計算系統、環境、和/或配置的示例包括但不限於，個人計算機、伺服器計算機、手持式或膝上型設備(例如，媒體播放器、筆記本計算機、蜂窩電話、個人數字助理、語音記錄器)、多處理器系統、基於多處理器的系統、機頂盒、可編程消費電子產品、網絡PC、微型計算機、大型計算機、包括任何以上系統或設備的分布式計算環境等等。圖6示出合適的計算系統環境的示例。計算系統環境只是合適的計算環境的一個示例，而非意在對本發明的技術的使用範圍或功能提出任何限制。也不應將該計算環境解釋為對示例性操作環境中示出的任一組件或其組合有任何依賴性或要求。參考圖6，用於實現自動社交網絡圖挖掘和可視化技術的示例性系統包括諸如計算設備600等計算設備。在其最基本的配置中，計算設備600通常包括至少一個處理單元602和存儲器604。取決於計算設備的確切配置和類型，存儲器604可以是易失性的(如RAM)、非易失性的(如ROM、快閃記憶體等)或是兩者的某種組合。該最基本配置在圖6中由虛線606來例示。另外，設備600還可具有附加特徵/功能。例如，設備600還可包含附加存儲(可移動和/或不可移動)，包括但不限於磁碟、光碟或磁帶。這些其它存儲在圖6中由可移動存儲608和不可移動存儲610示出。計算機存儲介質包括以用於存儲諸如計算機可讀指令、數據結構、程序模塊或其它數據等信息的任何方法或技術來實現的易失性和非易失性、可移動和不可移動介質。存儲器604、可移動存儲608和不可移動存儲610都是計算機存儲介質的示例。計算機存儲介質包括但不限於，RAM、R0M、EEPR0M、快閃記憶體或其他存儲器技術、CD-ROM、數字多功能盤(DVD)或其他光存儲、磁帶盒、磁帶、磁碟存儲或其他磁存儲設備、或者可用於存儲所需信息並且可由設備600訪問的任何其他介質。計算機可讀介質包括瞬態的傳播信號和計算機(可讀)存儲介質。任何這樣的計算機存儲介質都可以是設備600的一部分。設備600還可包含允許該設備與其它設備以及網絡通信的通信連接612。通信連接612是通信介質的一個示例。通信介質通常以諸如載波或其它傳輸機制等已調製數據信號來體現計算機可讀指令、數據結構、程序模塊或其它數據，並包括任意信息傳送介質。術語「已調製數據信號」指的是其一個或多個特徵以在信號中編碼信息的方式被設定或更改，從而改變了信號的接收設備的配置或狀態的信號。作為示例而非限制，通信介質包括有線介質，諸如有線網絡或直接線連接，以及無線介質，諸如聲學、RF、紅外線和其他無線介質。如此處所使用的術語「計算機可讀介質」包括存儲介質和通信介質兩者。設備600可具有各種輸入設備614，如顯示器、鍵盤、滑鼠、筆、照相機、觸摸輸入設備等。還可包括諸如顯示器622、揚聲器、印表機等輸出設備616。所有這些設備在本領域中是公知的並且不必在此詳細討論。自動社交網絡圖挖掘和可視化技術可在由計算設備執行的諸如程序模塊等的計算機可執行指令的通用上下文中描述。一般而言，程序模塊包括執行特定任務或實現特定抽象數據類型的例程、程序、對象、組件、數據結構等等。自動社交網絡圖挖掘和可視化技術可以在任務由通過通信網絡連結的遠程處理設備執行的分布式計算環境中實現。在分布式計算環境中，程序模塊可以位於包括存儲器存儲設備在內的本地和遠程計算機存儲介質中。
還應當注意，可以按所需的任何組合來使用此處所述的上述替換實施例的任一個或全部以形成另外的混合實施例。儘管用結構特徵和/或方法動作專用的語言描述了本主題，但可以理解，所附權利要求書中定義的主題不必限於上述具體特徵或動作。上述具體特徵和動作是作為實現權利要求的示例形式公開的。
權利要求
1.一種用於標識實體之間的社交連接的計算機實現的過程，包括 使用計算設備來 接收標識實體之間的社交連接的一組網頁； 將每一網頁的內容解析成信息塊； 標識信息塊中實體的名稱； 考慮所述信息塊中名稱的位置以及環繞文本來對所述信息塊中的實體名稱之間的社交連接排序；以及 綜合來自所有信息塊中的已排序社交連接來確定與所述實體名稱相關聯的實體之間的連接的強度。
2.如權利要求I所述的計算機實現的過程，其特徵在於，還包括基於與所述實體名稱相關聯的實體之間的連接的強度創建社交網絡圖。
3.如權利要求I所述的計算機實現的過程，其特徵在於，對所述實體名稱之間的社交連接排序還包括使連接權重與實體名稱相關聯。
4.如權利要求I所述的計算機實現的過程，其特徵在於，解析每一網頁的內容包括使用視覺解析器來將所述內容解析成信息塊。
5.一種以創建2-D圖的形式來顯示從一般的網頁中提取的實體名稱之間的社交連接的系統，所述2-D圖具有一組表示名稱的頂點以及一組表示社交連接的邊，所述系統包括 通用計算設備； 包括能由所述通用計算設備執行的程序模塊的電腦程式，其中所述計算設備由所述電腦程式的程序模塊來引導以便 輸入社交圖所有者和附加實體之間的已排序的社交連接列表； 將所述社交圖所有者置於所述2D圖的中心作為中心頂點； 對所述已排序列表中的每一實體，將表示已排序列表中的實體的名稱的頂點置於所述中心頂點周圍的不同軌道中，其中軌道半徑越短，所述軌道中的頂點與所述中心頂點之間的社交連接越強； 根據所述頂點之間的連通性，將所述頂點聚集到不同的聚類中； 使用力指向模型來優化所述2D布局的均一性，其中所述力指向模型包括 每兩個頂點之間的排斥力； 所述邊之間的吸引力； 相鄰軌道之間的排斥力；以及 隔離彼此之間沒有連接的聚類的不可穿透邊界。
6.如權利要求5所述的系統，其特徵在於，每一頂點、邊、軌道和不可穿越邊界或者是徑向或切向自由的，或者是徑向和切向均自由的，以便允許根據力來移動。
7.如權利要求5所述的系統，其特徵在於，還包括用於在顯示器上顯示2D圖並允許用戶操縱所述2D圖的圖形用戶界面。
8.如權利要求5的系統，其特徵在於，所述圖形用戶界面還彩色顯示所述2D圖的頂點，其中彼此接近的頂點以類似顏色顯示。
9.如權利要求5所述的系統，其特徵在於，所述頂點的顏色根據所述頂點的位置的從0°到360°的極坐標改變。
10.如權利要求5所述的系統，其特徵在於，所述圖形用戶界面還包括動畫，所述動畫包括當用戶選擇頂點時所述2D圖將改變成新2D圖。
全文摘要
此處描述的自動社交網絡圖挖掘和可視化技術從一般(不必是社交應用專用的)網頁挖掘社交連接並允許創建社交網絡圖。該技術使用一個或多個網頁上一人/實體的名稱和相關人/實體的名稱之間的距離來確定各人/實體之間的連接以及這些連接的強度。在一個實施例中，該技術通過使用力指向模型對這些連接進行布局，然後將這些連接聚集在表示相關的人或實體的名稱之間的Web連接強度的社交網絡圖的2-D布局中。
文檔編號G06F17/27GK102893275SQ201180023860
公開日2013年1月23日 申請日期2011年5月10日 優先權日2010年5月14日
發明者聶再清, 曹湧, 羅剛, 張若馳, 劉曉江, 馬雲霄, 張波, 徐迎慶, 文繼榮 申請人:微軟公司