圖上的有效資源分配 - 群眾外包

Abstract

群眾外包是社群與網路科學中新崛起的科技，然而現存的研究大多不考慮群眾工作者自由選擇想處理的子任務對一個群眾外包系統的效能與子任務品質的影響。本篇論文考慮這個社群網路中的基本現象，並將此概念抽象化成在圖上的隨機漫步，因此，群眾外包系統的效能就是圖的平均覆蓋時間 (mean cover time)，而子任務的品質則可由佔用測度 (occupation measure) 來描述。藉此，我們提出最佳子任務管理與推薦問題，也就是利用連結子任務，在滿足子任務品質與成本限制下最佳化系統的效率。這個最佳子任務管理與推薦問題也可被視為圖上的有效資源分配問題。利用光譜圖論 (Spectral graph theory) 與次模集合函數 (Submodular set function) 優化理論，我們提出了清晰簡潔且運算可行的方法論來解決這個問題，並利用數值模擬與真實數據驗證了它們的正確性與效率。這個方法論在其他眾多領域，如：網路中的搜尋與導航、資源獲取、感測器規畫問題等也具有廣泛的應用。

Crowdsourcing has been an emerging technology in social and network science. Existing researches, however, often neglect the underlying tasks selection process of crowd workers, and how it effects the efficiency and tasks quality of a crowdsourcing system. In this thesis, we consider and formulate this fundamental phenomenon as random walks over graphs; Hence, the efficiency and quality are connected to the mean cover time and occupation measure on graphs respectively. We propose the optimal tasks management and recommendation problem, which could be viewed as a resource allocation problem over graphs, and aim at reducing the mean cover time while satisfying some quality constraints {it via} adding edges efficiently among tasks. Exploiting graph spectrum and submodular set function optimization, elegant and computationally efficient methodologies are proposed to implement such systems, together with illustrative verification from numerical results and data of real crowdsourcing systems. This methodology could be applied to numerous applications in other fields, including network searching and navigation, resource harvesting, sensor distributing problems, etc..