Öznitelikli Ağlarda Topluluk Arama

Öz

Sosyal ağların yoğun bir şekilde kullanımıyla birlikte, bir dizi sosyal nesnelerden ve nesnelere ait sosyal etkileşimlerden oluşan geniş ölçekli karmaşık ağ yapıları ortaya çıkmaktadır. Son zamanlarda, bu büyük ağ yapılarını analiz etmek için ağlardaki anlamlı grupları diğer bir deyişle toplulukları arama yaklaşımları önerilmektedir. Topluluk arama, sorgu nesneleri kullanarak, karmaşık ağ yapılarından sorgu nesneleri ile ilişkili, belli özellikler açısından birbirleri ile benzerlik gösteren ve birbirleri ile yoğun etkileşimde olan toplulukları ortaya çıkarma problemidir. Öznitelikli ağlar, düğümleri ağ nesnelerini, kenarları bu nesneler arasındaki ilişkileri temsil eden graf yapılarından ve ağdaki düğümleri karakterize eden içerik verisi diğer bir deyişle özniteliklerden oluşmaktadır. Geleneksel topluluk arama yaklaşımları, düğümlere ait öznitelik verisini göz ardı ederek, sadece ağ topolojisine odaklanmaktadır. Bu çalışmada, öznitelikli ağlarda topluluk arama problemi için öznitelik verisini ağ topolojisine entegre etme fikrine dayanan yeni bir yaklaşım öneriyoruz. Önerilen yöntem, her düğümün yalnızca kendi öznitelikleriyle bağlı olduğu yeni bir graf temsili oluşturarak, ağ topolojisine içeriksel bir boyut eklemektedir. Bu çalışmada, mevcut topluluk arama algoritmalarını öznitelikli ağlar üzerinde uygulanabilir hale getirmek, bu algoritmaların başarısını artırmak ve öznitelik verisini sorgu verisi olarak kullanılabilir hale getirmek amaçlanmaktadır. Gerçek dünya veri setleri üzerinden elde edilen deneysel sonuçlar, önerilen yöntemin temel yöntemler ile karşılaştırıldığında daha yüksek doğruluk değerleri elde ettiğini göstermektedir.

Anahtar Kelimeler

• Öznitelikli ağlar
• topluluk arama
• k-tras
• k-çekirdek

Community Search on Attributed Networks

Abstract

With the intense use of social networks and information networks, large-scale complex networks are emerging, consisting of a number of social objects (such as individuals or organizations) and social interactions of these social actors. Recently, many community search methods have been proposed to analyze these network structures and interactions between network objects. Given one or more query objects, community search is the problem of discovering a subset of objects, called as community, that are related to query objects which are similar to each other in terms of certain properties and intensely interact with each other. A network is characterized by a graph structure whose nodes represent the network objects and the edges refer to the relations between these objects. An attributed network contains contextual information that defines the interests of network objects as well as the graph structure. However, traditional community search approaches focus on the network topology, ignoring the attribute data. In this paper, we propose a new approach for the community search problem in attribute networks, based on the idea of integrating the attribute data into the network topology. The proposed method adds a contextual dimension to the network topology by creating a bipartite graph structure where each node is connected only by its attributes. In this study, we aim to make existing community search algorithms applicable on attribute networks, to increase the accuracy of these algorithms and to make the attribute data usable as query data. Experimental results on real world datasets show that the proposed method achieves higher accuracy than baseline methods.

Keywords

• Attributed Networks
• Community Search
• k-truss
• k-core

Kaynakça

1. Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical review E, 80(5), 056117.
2. Chunaev, P. (2020). Community detection in node-attributed social networks: a survey. Computer Science Review, 37, 100286..
3. Kakisim, A., & Sogukpinar, I. (2015, May). Community detection in social networks using content and link analysis. In 2015 23nd Signal Processing and Communications Applications Conference (SIU) (pp. 1521-1524). IEEE.
4. He, K., Li, Y., Soundarajan, S., & Hopcroft, J. E. (2018). Hidden community detection in social networks. Information Sciences, 425, 92-106.
5. Ma, T., Liu, Q., Cao, J., Tian, Y., Al-Dhelaan, A., & Al-Rodhaan, M. (2020). LGIEM: Global and local node influence based community detection. Future Generation Computer Systems, 105, 533-546.
6. Huang, X., Lakshmanan, L. V., & Xu, J. (2017, April). Community search over big graphs: Models, algorithms, and opportunities. In 2017 IEEE 33rd international conference on data engineering (ICDE) (pp. 1451-1454). IEEE.
7. Huang, X., Lakshmanan, L. V., & Xu, J. (2019). Community search over big graphs. Synthesis Lectures on Data Management, 14(6), 1-206.
8. Huang, X., & Lakshmanan, L. V. (2017). Attribute-driven community search. Proceedings of the VLDB Endowment, 10(9), 949-960.

9. Shang, J., Wang, C., Wang, C., Guo, G., & Qian, J. (2017). An attribute-based community search method with graph refining. The Journal of Supercomputing, 1-28.
10. Barbieri, N., Bonchi, F., Galimberti, E., & Gullo, F. (2015). Efficient and effective community search. Data mining and knowledge discovery, 29(5), 1406-1433.
11. Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014, June). Querying k-truss community in large and dynamic graphs. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data (pp. 1311-1322).
12. Yuan, L., Qin, L., Lin, X., Chang, L., & Zhang, W. (2016). Diversified top-k clique search. The VLDB Journal, 25(2), 171-196.
13. Chang, L., Lin, X., Qin, L., Yu, J. X., & Zhang, W. (2015, May). Index-based optimal algorithms for computing steiner components with maximum connectivity. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (pp. 459-474).
14. Zhang, Q., Li, R. H., Yang, Q., Wang, G., & Qin, L. (2020, April). Efficient top-k edge structural diversity search. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) (pp. 205-216). IEEE.
15. Sun, H., Huang, R., Jia, X., He, L., Sun, M., Wang, P., ... & Huang, J. (2020). Community search for multiple nodes on attribute graphs. Knowledge-Based Systems, 193, 105393.
16. Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020). A survey of community search over big graphs. The VLDB Journal, 29(1), 353-392.
17. LNQS, (2021). Statistical Relational Learning Group, (https://linqs.soe.ucsc.edu/data), (Erişim Tarihi: 07.05.2021).