如何將大型二部圖用戶項目轉換爲項目項目？

Question

我有一個非常大的（10M +邊緣，〜5M頂點）二分無向用戶項圖形格式

item1: user1, user2, user3, ... 

或

userX1: itemY1 
userX2: itemY2 
... 

我需要我的圖形轉換成項目，項目圖其中i和j頂點之間的邊的權重等於同時使用這兩個項的用戶的數量（即，與item_i和item_j相鄰的頂點集合的交集中的元素的數量）。這裏有一個問題，它似乎需要我做$ O（n^2）$操作，其中$ n $是圖中邊緣的數量，在我現在的簡單家用電腦上是不可能的。有沒有解決這個問題的方法？一些概率數據結構將適合我的需要，因爲我被允許丟失一小部分數據。

Answer 1

符號：M =舊圖

1. 排序的邊列表E（兩張您提出的格式版本）的用戶邊數（花費O（M日誌（M））
2. 圍棋通過E並確定所有連續邊緣與相同用戶（O（m））的運行
3. 運行中的每對邊緣在新圖形中爲您提供邊緣 - >將其添加到新圖形的邊緣列表F （O（| F | = n_user x max_n_items_per_user^2））
4. 契約F所有重複成單邊緣與由副本的數目給出的邊緣權重（O（| F |））

如果您的曲線圖是稀疏的，即max_n_items_per_user小，上述應該是相當高效。否則，這個算法存在一個問題，即它在收縮它們之前枚舉新圖中的所有邊，所以應該考慮如何直接獲得邊權。