在現實生活中使用者透過Facebook社群網站分享資訊時，為了管理分享資訊的散播，此時可以針對分享資訊個別選擇特定的朋友，可是當特定的朋友數越多時會讓造成使用者花費更多的管理成本，所以為了方便分享資訊時的操作，在Facebook 社群網路允許使用者將朋友分至特定的朋友名單，讓使用者在分享資訊時就能限制朋友名單中的所有朋友，簡化操作，此外雖然可以透過智慧型清單或自動分群機制能協助朋友名單管理，然而過去不論是智慧型清單或自動分群機制皆是將相似的朋友直接分成相同群組，卻未考量到朋友之間彼此衝突的情況。

因此本研究提出考量互斥因子之自動分群機制，主要是比較多種分群演算法進行群組適當性和時間複雜度的探討，最後選擇 BGLL 分群演算法為基礎進行改良，主要考量到朋友之間彼此衝突的情況，讓使用者提供回饋資訊進行條件設定之後，再針對使用者在Facebook社群網路中之個人網路進行分群，此時將會產生符合使用者回饋資訊的需求條件的群組。

然而在分群群組的評估分析上，過往研究者主要是透過評估指標進行比較分析，因為若要請大量使用者直接針對所有群組進行評估，在實驗上會非常的困難，所以少有研究是直接根據使用者回饋進行比較分析。所以本研究會實作系統協助使用者針對考量互斥因子之自動分群機制產生的群組進行直接的調整，待確認之後即時透過資訊檢索領域中廣泛被應用的查準率與查全率進行比較分析。

When users use social network services, such as Facebook, Twitter and Google+, to share information, users may cluster their friends into groups and share information based on the groups to reduce costs of setting who can access the information. In this case, the more friends a user has, the more cost the user needs to put the user’s friends into groups.

Therefore, researchers develop approaches to help users to cluster or group their friends in social network services automatically. For example, Facebook provides a function to put friends of a user into friend lists based on user profiles. Therefore, users can restrict the information to be accessed by friends in selected friend lists. However, current automatic friends grouping researches focus on the similarity among user friends. We may consider conflicts among friends to increase effectiveness of friends grouping.

In addition to similarity among friends of users, this paper proposes a novel approach to group friends of users in social network services considering conflicts among friends. After comparing several current friends grouping approaches, this study select BGLL as basis and extend BGLL to consider conflicts among friends. This research further implements a system to help users consider conflicts among friends and put their friends into groups based on the proposed approach automatically.

Finally, current researches usually do not collect user feedback to evaluate effectiveness of grouping results directly. This paper proposes a method to evaluate precision and recall of friend grouping approaches base on user feedback. Therefore, this research also contributes to provide a scheme for evaluating effectiveness of friend grouping approaches in social network services.

[1]. 創市際公佈「2012年網路社群白皮書」調查報告. (2012).
http://www.insightxplorer.com/news/news_12_18_12.html
[2]. Li, W. (2012). Research on the design of social spheres in social network sites.
[3]. Facebook 使用說明中心 (2013).
https://www.facebook.com/help/
[4]. Ellison, N. B. (2007). Social network sites: Definition, history, and scholarship. Journal of Computer‐Mediated Communication, 13(1), 210-230.
[5]. Ugander, J., Karrer, B., Backstrom, L., & Marlow, C. (2011). The anatomy of the facebook social graph. arXiv preprint arXiv:1111.4503.
[6]. McAuley, J., & Leskovec, J. (2012). Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems 25 (pp. 548-556).
[7]. Staddon, J., Huffaker, D., Brown, L., & Sedley, A. (2012). Are privacy concerns a turn-off?: engagement and privacy in social networks. In Proceedings of the Eighth Symposium on Usable Privacy and Security (p. 10). ACM.
[8]. Liu, Y., Viswanath, B., Mondal, M., Gummadi, K. P., & Mislove, A. (2012). Simplifying friendlist management. In Proceedings of the 21st international conference companion on World Wide Web (pp. 385-388). ACM.
[9]. Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012). Community detection in social media. Data Mining and Knowledge Discovery, 24(3), 515-554.
[10]. Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008.
[11]. Chaturvedi, P., Dhara, M., & Arora, D. (2012). Community Detection in Complex Network via BGLL Algorithm. International Journal of Computer Applications.
[12]. Lampinen, A., Tamminen, S., & Oulasvirta, A. (2009). All my people right here, right now: management of group co-presence on a social networking site. In Proceedings of the ACM 2009 international conference on Supporting group work (pp. 281-290). ACM.
[13]. Skeels, M. M., & Grudin, J. (2009). When social networks cross boundaries: a case study of workplace use of facebook and linkedin. In Proceedings of the ACM 2009 international conference on Supporting group work (pp. 95-104). ACM. Jones, S., & O'Neill, E. (2010, July).
[14]. Agarwal, G., & Kempe, D. (2008). Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B, 66(3), 409-418.
[15]. Manning, C. D., Raghavan, P., & Schutze, H. (2008). Introduction to information retrieval (Vol. 1). Cambridge: Cambridge University Press.
[16]. van Rijsbergen, C. J. (1977). A theoretical basis for the use of co-occurrence data in information retrieval. Journal of documentation, 33(2), 106-119.
[17]. Chen, J., Zaiane, O., & Goebel, R. (2009). Local community identification in social networks. In Social Network Analysis and Mining, 2009. ASONAM'09. International Conference on Advances in (pp. 237-242). IEEE.
[18]. Grob, R., Kuhn, M., Wattenhofer, R., & Wirz, M. (2009). Cluestr: mobile social networking for enhanced group communication. In Proceedings of the ACM 2009 international conference on Supporting group work (pp. 81-90). ACM.
[19]. Mislove, A., Viswanath, B., Gummadi, K. P., & Druschel, P. (2010). You are who you know: inferring user profiles in online social networks. In Proceedings of the third ACM international conference on Web search and data mining (pp. 251-260). ACM.
[20]. Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications (Vol. 8). Cambridge university press.
[21]. Chung, K. K., Hossain, L., & Davis, J. (2005). Exploring sociocentric and egocentric approaches for social network analysis. In Proceedings of the 2nd international conference on knowledge management in Asia Pacific.
[22]. Tang, L., & Liu, H. (2010). Community detection and mining in social media. Synthesis Lectures on Data Mining and Knowledge Discovery, 2(1), 1-137.
[23]. JIS, M. T. C. S. (1979). Computers and intractability A Guide to the Theory of NP-Completeness.
[24]. Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., & Wagner, D. (2008). On modularity clustering. Knowledge and Data Engineering, IEEE Transactions on, 20(2), 172-188.
[25]. Girvan, M., & Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12), 7821-7826.
[26]. Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 452-473.
[27]. Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.
[28]. Newman, M. E. (2004). Fast algorithm for detecting community structure in networks. Physical review E, 69(6), 066133.
[29]. Clauset, A., Newman, M. E., & Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6), 066111.
[30]. Ovelgonne, M., Geyer-Schulz, A., & Stein, M. (2010). 0 greedy modularity optimization for group detection in huge social networks. In SNA-KDD’10: Proceedings of the 4th Workshop on Social Network Mining and Analysis.
[31]. Smyth, S., & White, S. (2005). A spectral clustering approach to finding communities in graphs. In Proceedings of the fifth SIAM international conference on data mining (Vol. 119, p. 274).
[32]. Fortunato, S., & Barthelemy, M. (2007). Resolution limit in community detection. In Proceedings of the National Academy of Science (Vol. 104, pp. 36-41).
[33]. Xu, X., Yuruk, N., Feng, Z., & Schweiger, T. A. (2007). SCAN: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 824-833). ACM.
[34]. Leung, I. X., Hui, P., Lio, P., & Crowcroft, J. (2009). Towards real-time community detection in large networks. Physical Review E, 79(6), 066107.
[35]. Jin, D., Liu, D., Yang, B., Liu, J., & He, D. (2011). Ant colony optimization with a new random walk model for community detection in complex networks. Advances in Complex Systems, 14(05), 795-815.
[36]. Nadkarni, A., & Hofmann, S. G. (2012). Why do people use Facebook?. Personality and individual differences, 52(3), 243-249.
[37]. DiMicco, J. M., & Millen, D. R. (2007). Identity management: multiple presentations of self in facebook. In Proceedings of the 2007 international ACM conference on supporting group work (pp. 383-386). ACM. Hewitt, A., & Forte, A. (2006).
[38]. Wilson, R. E., Gosling, S. D., & Graham, L. T. (2012). A review of Facebook research in the social sciences. Perspectives on Psychological Science, 7(3), 203-220.
[39]. Das, S., & Kramer, A. (2013). Self-Censorship on Facebook.
[40]. Lusseau, D. (2003). The emergent properties of a dolphin social network. Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(Suppl 2), S186-S188.
[41]. Gleiser, P. M., & Danon, L. (2003). Community structure in jazz. Advances in complex systems, 6(04), 565-573.
[42]. Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., & Arenas, A. (2003). Self-similar community structure in a network of human interactions. Physical review E, 68(6), 065103.
[43]. Ferrara, E. (2012). A large-scale community structure analysis in Facebook. EPJ Data Science, 1(1), 1-30.
[44]. Gregory, S. (2010). Finding overlapping communities in networks by label propagation. New Journal of Physics, 12(10), 103018.
[45]. Wu, Z., Lin, Y., Wan, H., Tian, S., & Hu, K. (2012). Efficient overlapping community detection in huge real-world networks. Physica A: Statistical Mechanics and its Applications, 391(7), 2475-2490.
[46]. Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4), 046110.
[47]. Fortunato, S., & Lancichinetti, A. (2009). Community detection algorithms: a comparative analysis: invited presentation, extended abstract. In Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools (p. 27). ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering).
[48]. Steinhaeuser, K., & Chawla, N. V. (2010). Identifying and evaluating community structure in complex networks. Pattern Recognition Letters, 31(5), 413-421.
[49]. Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336), 846-850.
[50]. Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of classification, 2(1), 193-218.
[51]. Ana, L. N. F., & Jain, A. K. (2003). Robust data clustering. In Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on (Vol. 2, pp. II-128). IEEE.
[52]. Jones, S., & O'Neill, E. (2010). Feasibility of structural network clustering for group-based privacy control in social networks. In Proceedings of the Sixth Symposium on Usable Privacy and Security (p. 9). ACM.
[53]. Hammer-Lahav, E., Recordon, D., & Hardt, D. (2011). The OAuth 2.0 authorization protocol. Network Working Group Internet-Draft.
[54]. Triola, M. F. (2008). Essentials of statistics. Boston: Pearson Addison Wesley.
[55]. Nielsen, J. (1994). Usability engineering. Access Online via Elsevier.
[56]. DATA SCIENCE OF THE FACEBOOK WORLD (2013).
http://blog.wolframalpha.com/2013/04/24/data-science-of-the-facebook-world/