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

Etki Enbüyükleme Problemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zor bir stokastikkombinatoryal 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ış modelleriile tasarlandığında, elde edilen problemin amaç fonksiyonunun alt-birimsel olduğu gözlemlenmiştir. Busebeple 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öntemarayışlarına neden olmuştur. Son yıllarda geliştirilen yeni yöntemler genelde büyük boyutlu ağlarda kısasü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ı veEEP’yi eniyi / eniyiye yakın çözen ve ölçeklenebilen bir yöntem geliştirilmiştir. Bu çerçevede, öncelikleÖrneklem Ortalama Yakınsaması ile özgün probleme yakınsayan belirgin bir matematiksel modelkurulmuştur. Daha sonra bu model üzerinde düğüm tabanlı 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şitliboyutlardaki sosyal ağ veri setleri (Facebook, Enron, Gnutella, arXiv) üzerinde test edilmiştir. Bütünsenaryolarda eniyi / eniyiye yakın çözümlere ulaşılırken yazındaki mevcut yöntemlere göre on katakadar hızlanma sağlanmıştır.

An Efficient Lagrangean Relaxation Based Solution Method For Large Scale Influence Maximization Problem

The Influence Maximization Problem (IMP) is defined as identifying the most influential K individuals in a social network, which is a challenging stochastic combinatorial optimization problem. IMP has attracted great interest among researchers in the last years and many efficient solution methods for this problem has been developed. Under IMP the flow of information through the social network is assumed to be following certain information diffusion models and in certain cases the resulting objective function of the optimization problem is a sub-modular function. Therefore, a naive greedy heuristic can achieve a (1-1/e) worst-case bound. However, the greedy method is not scalable and results in very long computation time for large social networks. Upon this observation, many researchers proposed fast and scalable heuristics that still preserve the (1-1/e) worst-case bound. Contrarily, very few researchers focused on finding methods that provide optimal solutions to IMP. In this work a Lagrangean Relaxation based, fast and scalable method that provides optimal / close-tooptimal solutions is proposed. First, a deterministic optimization problem is constructed by using Sample Average Approximation for the original problem. Then, a node based Lagrangean Relaxation approach is developed to solve the approximation of the original problem. The method is tested with both Independent Cascade and Linear Threshold information diffusion models over various size reallife network instances (Facebook, Enron, Gnutella, arXiv). In all scenarios optimal / close-to-optimal solutions are obtained and our approach outperforms the state-of-the-art approaches up to ten times in terms of solution time.

PDF

___

Chen, W., Wang, Y. and Yang, S., 2009. Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International conference on Knowledge Discovery and Data Mining, ACM, 199- 208.
Fischer, M., 1981. The lagrangian relaxation method for solving integer programming problems. Management Science, 27, 1-18.
Galhotra, S., Arora, A. and Roy, S., 2016. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, ACM, 743-758.
Goldenberg, J., Libai, B. and 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.
Gurobi Optimization, 2019, Gurobi 8.0 User’s Manual.
Güney, E., 2019. On the optimal solution of budgeted influence maximization problem in social networks. Operational Research, 19, 817-831.
Güney, E., 2019. An efficient linear programming based method for the influence maximization problem in social networks. Information Sciences, 503, 589-605.
Günneç., D., 2018. Etki Enbüyükleme Problemi için Ajanbazlı 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.
Günneç, D., Raghavan, S., Zhang.,R. 2019. Least Cost Influence Maximization on Social Networks. Informs Journal on Computing, (Online First), https://doi.org/10.1287/ijoc.2019.0886 , 1-15.
Gürsoy, F. and Günneç, D., 2018. Influence Maximization in Social Networks under Deterministic Linear Threshold Model. Knowledge-Based Systems, 161, 111-123.
Homem-de-Mello, T. and Bayraksan, G., 2014. Monte carlo sampling-based methods for stochastic optimization. Surveys in Operations Research and Management Science, 19, 56-85.
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.
Ko, Y.Y., Cho, K.J. and Kim, S.W., 2018. Efficient and effective influence maximization in social networks: A hybrid-approach. Information Sciences, 465, 144-161.
Kumar, A., Wu, X. and Zilberstein, S., 2012. Lagrangian relaxation techniques for scalable spatial conservation planning. Proceedings of the Twenty- Sixth AAAI Conference on Artificial Intelligence, 439, 309-315.
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J. and Glance, 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.
Li, Y., Fan, J., Wang, Y. and Tan, K. L., 2018. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 1, 1852-1872.
Nguyen, H. T., Thai, M. T. and Dinh, T. N., 2016. Stop-andstare: Optimal sampling algorithms for viral marketing in billion-scale networks. Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, ACM, 695-710.
Peng, S., Zhou, Y., Cao, L., Yu, S., Niu, J. and Jia, W., 2018. Influence analysis in social networks: A survey. Journal of Network and Computer Applications, 106, 17-32.
Tang, Y.,Shi, Y.,and Xiao, X., 2015. Influence maximization in near-linear time: A martingale approach. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD15, ACM, 1539-1554.
Wu, H. H. and Küçükyavuz, S., 2017. A two stage stochastic programming approach for influence maximization in social networks. Computational Optimization and Applications, 69, 1-33.
1-http://snap.stanford.edu/data), (09.06.2019)