二分圖的應用有哪些？

在二分圖中，頂點可以分成兩個不相交的集合，使得每條邊都連線一個集合中的頂點和另一個集合中的頂點。對於AllElectronics使用者的購買資料，一個頂點集合定義使用者，每個頂點代表一個使用者。另一個集合定義產品，每個頂點代表一個產品。一條邊連線一個使用者和一個產品，表示使用者購買了該產品。

二分圖有各種各樣的應用，如下所示：

網路搜尋引擎：在網路搜尋引擎中，搜尋日誌被存檔為使用者查詢資料和相應的點選資料。（點選資料告訴我們，在給定搜尋結果的情況下，使用者點選了哪些頁面。）

查詢和點選資料可以使用二分圖來定義，其中兩個頂點集合分別對應查詢和網頁。

如果使用者在發出查詢時點選了網頁，則一條邊連線查詢和網頁。透過對查詢-網頁二分圖進行聚類分析，可以獲得有價值的資料。

例如，如果每個查詢的點選資料相同，則可以識別出用多種語言提出的但含義相同的查詢。網路上的一些網頁形成了一個有向圖，也稱為網路圖，其中每個網頁是一個頂點，每個超連結是一條邊，表示從源頁面到目標頁面的連結。對網路圖進行聚類分析可以識別社群，發現中心節點和權威網頁，並識別網路垃圾郵件。

社交網路：社交網路是一種社會結構。它可以定義為一個圖，其中頂點是人或組織，連線是頂點之間的相互依賴關係，描述友誼、共同興趣或合作活動。AllElectronics使用者形成了一個社交網路，其中每個使用者都是一個頂點，如果兩個使用者互相認識，則一條邊連線這兩個使用者。

作為使用者關係管理器，它有興趣透過聚類分析從AllElectronics的社交網路中發現有用的資料。它可以從網路中獲取聚類，其中聚類中的使用者互相認識或有共同的朋友。

叢集內的使用者可以在購買決策方面相互影響。此外，可以建立溝通渠道來指導叢集的“負責人”，以便快速推廣資訊。

該網路是一個加權圖，因為兩個作者之間的邊可以產生一個權重，定義合作的強度，包括兩個作者（作為端點頂點）共同撰寫的出版物數量。

Ginni

更新於：2022年2月18日

2K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習