Büyük Ölçekli Etki Enbüyükleme Problemi İçin Lagrange Gevşetmesi Tabanlı Etkin Bir Çözüm Yöntemi

Year 2020, , 47 - 58, 17.03.2020

Evren Güney

https://doi.org/10.35414/akufemubid.621330

Abstract

Etki Enbüyükleme
Problemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zor
bir stokastik kombinatoryal eniyileme problemidir. Son yıllarda pek çok
araştırmacının ilgisini çeken bu problem için çok sayıda etkin yöntem
geliştirilmiştir. Sosyal ağdaki bilginin / etkinin yayılımı çeşitli ağ akış
modelleri ile tasarlandığında, elde edilen problemin amaç fonksiyonunun
alt-birimsel olduğu gözlemlenmiştir. Bu sebeple basit bir açgözlü algoritma ile
(1-1/e) en kötü performans garantisine erişilmiştir. Ancak, aç gözlü
algoritmanın büyük boyutlu problemlerde çok uzun çözüm süreleri gerektirmesi
alternatif yöntem arayışlarına neden olmuştur. Son yıllarda geliştirilen yeni
yöntemler genelde büyük boyutlu ağlarda kısa sürede iyi çözümler elde ederken
(1-1/e) performans garantisini de korumaktadır. Ancak pek az sayıda çalışma
problemin sadece en-iyi çözümüne odaklanmıştır. Bu çalışmada Lagrange
gevşetmesi tabanlı ve EEP’yi optimal / optimale yakın çözen ve ölçeklenebilen bir
yöntem geliştirilmiştir. Bu çerçevede öncelikle, Örneklem Ortalama
Yaklaşıklaması ile orijinal probleme yakınsayan belirgin bir matematiksel model
kurulmuştur. Daha sonra bu model üzerinde düğüm bazlı Lagrange gevşetmesi
tekniği uygulanmıştır. İlgili yöntem bağımsız çağlayan ve doğrusal eşik bilgi
yayılım modelleri varsayımı altında çeşitli boyutlardaki sosyal ağ veri setleri
(Facebook, Enron, Gnutella, arXiv) üzerinde test edilmiştir. Bütün senaryolarda
optimal / optimale yakın çözümlere ulaşılırken literatürdeki mevcut yöntemlere
göre en az bir ölçek mertebesinde hızlanma sağlanmıştır.

Keywords

Etki Enbüyüklemesi, Sosyal Ağlar, Stokastik Eniyileme, Lagrange Gevşetmesi

Supporting Institution

Tübitak-Teydeb

Project Number

1507- 7150022

References

• Li, Y., Fan, J., Wang, Y., Tan, K. L., 2018, Influence maximization on social graphs: A survey, IEEE Transactions on Knowledge and Data Engineering, 1, 1852-1872.
• Günneç., D., Etki Enbüyükleme Problemi için Ajan-bazlı Modelleme Yaklaşımı (An Agent-based Modeling Approach for the Influence Maximization Problem). Afyon Kocatepe Üniversitesi Fen ve Mühendislik Bilimleri Dergisi, 18, 701-709, 2018
• Peng, S., Zhou, Y., Cao, L., Yu, S., Niu, J., Jia, W., 2018, Influence analysis in social networks: A survey, Journal of Network and Computer Applications, 106, 17-32.
• Kempe, D., Kleinberg, J. and Tardos, E., 2003. Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge Discovery and Data Mining, ACM, 137-146.
• Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J. andGlance, N., 2007. Cost effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD International conference on Knowledge Discovery and Data Mining,ACM, 420-429
• Chen, W., Wang, Y. andYang, S., 2009. Efficient influence maximization in social networks.Proceedings of the 15th ACM SIGKDD International conference on Knowledge DiscoveryandData Mining, ACM, 199-208
• Galhotra, S., Arora, A., Roy, S., 2016, Holistic influence maximization: Combining scalability and efficiency with opinion-aware models, in: Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, ACM, New York, 743-758.
• Tang, Y.,Shi, Y.,andXiao, X., 2015. Influence maximization in near-linear time: A martingale approach, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD15, 1539-1554, New York, NY, USA, ACM.
• Ko, Y.-Y. Cho, K.-J. Kim, S.-W., 2018, Efficient and effective influence maximization in social networks: A hybrid-approach, Information Sciences, 144-161.
• Nguyen, H. T. Thai, M. T. Dinh, T. N., 2016, Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks, in: Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, ACM, NY.
• Güney, E., 2017, On the optimal solution of budgeted influence maximization problem in social networks, Operational Research, 1-14. doi:10.1007/s12351-017-0305-x
• Güney, E., 2019, An efficient linear programming based method for the influence maximization problem in social networks, Information Sciences, 503, 589-605.
• Wu, H. H., Küçükyavuz, S., 2017. A two stage stochastic programming approach for influence maximization in social networks, Computational Optimization and Applications, 1-33
• Gursoy, F., Gunnec, D., 2018, Influence Maximization in Social Networks under Deterministic Linear Threshold Model. Knowledge-Based Systems, 161, 111-123.
• Gunnec, D., Raghavan, S., Zhang.,R. 2019, Least Cost Influence Maximization on Social Networks. Informs Journal on Computing (accepted).
• Goldenberg, J., Libai, B., Muller, E., 2001, Talk of the network: A complex systems look at the underlying process of word-of-mouth, Marketing Letters, 211-223.
• Granovetter, M., 1978, Threshold models of collective behaviour, The American Journal of Sociology, 83, 1420-1443.
• Homem-de-Mello, T., Bayraksan, G., 2014, Monte carlo sampling-based methods for stochastic optimization, Surveys in Operations Research and Management Science, 19, 56-85.
• Fischer, M., 1981, The lagrangian relaxation method for solving integer programming problems, Management Science 27, 1-18.
• Kumar, A., Wu, X., Zilberstein, S., 2012, Lagrangian relaxation techniques for scalable spatial conservation planning, in: AAAI,439, 309-315.
• Gurobi Optimization, 2019, Gurobi 8.0 User’s Manual.