在社交網絡中的朋友進行分類

Question

我現在面臨壽以下問題：
假設ü是社交網絡用戶，因此有很多朋友，F（U）列表。 分區是函數F-> G，其中G是一組組，如高中，大學，工作等。
我需要拿出算法三方˚F：

• 輸入是˚F也F（F）在爲每˚F˚F（的朋友列表每個或的朋友）。
• 運行過程中允許算法詢問ü問題（例如「什麼是某些特定用戶的最佳羣體v？」）。
• 問題的數量應該保持在最小值（什麼是最小值不是一個真正的數字，但我認爲5％的朋友的數量似乎是正確的）。

顯然得到的分區不是最優的，但它應該是可以接受的作爲以後改進的起點。

任何想法，將不勝感激

編輯：不，這不是功課。我相信家庭作業會有更明確的要求和目標功能。無論如何不，這實際上是我面臨的現實世界問題。

也i可以具有簡化的有點，但在現實中，用戶可以是許多基團的一部分（這樣它更像F-> P（G），其中P（G）是功率組如果G），所以更好的算法將能夠做到這一點。

Answer 1

的基本想法是嘗試將它們劃分成基於組上你的朋友是朋友彼此。

例如，如果你是鮑勃，你知道Sally和拉里和Sally和拉里都知道對方，他們很可能是在同一個「組」。你不知道那團是什麼呢，不過既然你都知道對方，你可能是在同一個地方見面 - 不管是工作，大學等

您可以實現這個作爲向圖，其中的節點是人，邊是連接。然後，您需要根據它們的連接程度將這些節點組合在一起。

一旦你建立了組，那麼它只是一個查詢從羣體和潛在的曖昧節點樣本找出組實際上是問題。

聽起來像功課，所以我不會放棄任何東西，但應該讓你開始。