Willingness Maximization for Ego Network Data Extraction in Multiple Online Social Networks

Bay Yuan Hsu, Lo Yao Yeh, Ming Yi Chang, Chih Ya Shen

研究成果: 雜誌貢獻期刊論文同行評審


Egocentric network (ego network) data are very important for evaluating algorithms and machine learning approaches in Online Social Networks (OSNs). Nevertheless, obtaining the ego network data from OSNs is not a trivial task. Conventional manual approaches are time-consuming, and sometimes the ego network data are quite incomplete because only a small number of users would agree to provide their data. This is because there are two important factors that should be considered simultaneously for this data acquisition task: i) users' willingness to provide their data, and ii) the structure of the ego network. However, addressing the above two factors to obtain the more complete ego network data has not received much research attention. Therefore, in this paper, we address this issue by proposing a family of new research problems. The first proposed problem, named Willingness Maximization for Ego Network Extraction in Online Social Networks (WMEgo), identifies a set of ego networks from a single OSN, such that the willingness of the users to provide their data is maximized. We prove that WMEgo is NP-hard and propose a 12(1-1e)-approximation algorithm, named Ego Network Identification with Maximum Willingness (EIMW). Furthermore, we extend the idea of WMEgo to multiple social networks and formulate a new research problem, named Willingness Maximization on Multiple Social Networks for Ego Network Extraction (WM2Ego), which is able to effectively obtain ego network data from multiple social networks simultaneously. We propose a 12-approximation algorithm, named Maximum Expansion for UNified EXpenses (MUNEX) for a special case of WM2Ego and then design a constant-ratio approximation algorithm to the general WM22Ego problem, named Maximum Expansion with Expense Examination (M3E). We conduct two evaluation studies with 672 and 1,052 volunteers to validate the proposed WMEgo and WM2Ego problems, respectively, and show that they are able to obtain much more complete ego network data compared to other baselines. We also perform extensive experiments on multiple real datasets to demonstrate that the proposed approaches significantly outperform the other baselines.

頁(從 - 到)8672-8686
期刊IEEE Transactions on Knowledge and Data Engineering
出版狀態已出版 - 1 8月 2023


深入研究「Willingness Maximization for Ego Network Data Extraction in Multiple Online Social Networks」主題。共同形成了獨特的指紋。