Search

Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based on Benders decomposition is proposed and a relation between obtained Benders optimality cuts and submodular cuts for correspondingly defined subsets is established. We introduce preprocessing tests, which allow us to remove variables from the model and develop efficient algorithms for the separation of Benders cuts. Both aspects are shown to be crucial ingredients of the developed branch-and-cut algorithm since real-life social network instances may be very large. In a computational study, the considered variants of this branch-and-cut algorithm outperform the state-of-the-art approach for influence maximization by orders of magnitude.

The Influence Maximization Problem has been widely studied in recent years, due to rich application areas including marketing. It involves finding k nodes to trigger a spread such that the expected...

The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that converges to the current state-of-the-art 1 − 1 / e bound asymptotically. Experimental analysis indicate that the new method is superior to the state-of-the-art in terms of solution quality and this is one of the few studies that provides approximate optimal solutions for certain real life social networks.

The budgeted influence maximization problem is a challenging stochastic optimization problem defined on social networks. In this problem, the objective is identifying influential individuals who can influence the maximum number of members within a limited budget. In this work an integer program that approximates the original problem is developed and solved by a sample average approximation (SAA) scheme. Experimental analyses indicate that SAA method provides better results than the greedy method without worsening the solution time performance. © 2017, Springer-Verlag Berlin Heidelberg., TEYDEB-1507-7150022, This research has been supported by T?B?TAK (The Scientific and Technological Research Council of Turkey) under the Grant no: TEYDEB-1507-7150022.

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. 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.

Güney, Evren (Arel Author), Sensors are tiny electronic devices having limited battery energy and capability for sensing, data processing and communicating. They can collectively behave to provide an effective wireless network that monitors a region and transmits the collected information to gateway nodes called sinks. Most of the applications require the operation of the network for long periods of times, which makes the efficient management of the available energy resources an important concern. There are three major issues in the design of sensor networks: sensor deployment or the coverage of the sensing area, sink location, and data routing. In this work, we consider these three design problems within a unified framework and develop two mixed-integer linear programming formulations. They are difficult to solve exactly. However, it is possible to compute good feasible solutions of the sink location and routing problems easily, when the sensors are deployed and their locations in the sensor field become known. Therefore, we propose a tabu search heuristic that tries to identify the best sensor locations satisfying the coverage requirements. The objective value corresponding to each set of sensor locations is calculated by solving the sink location and routing problem. Computational tests carried out on randomly generated test instances indicate that the proposed hybrid approach is both accurate and efficient

Sensors spend most of their limited battery energy on communicating the collected environmental information to sinks. Therefore, the determination of the optimal sink locations and sensor-to-sink information flow routes becomes important for the survivability of sensor networks. In this work, we address these important design issues using an integrated approach and propose new mixed-integer linear programming models to determine the optimal sink locations and information flow paths between sensors and sinks when sensor locations are given. The first group of proposed models is energy-aware and tries to minimize total routing energy, whereas the second group is financially driven with the objective of minimizing total cost. We do not only report computational results providing information on the solution efficiency of the new formulations, and the accuracy of their linear programming relaxations, but also propose and test new heuristics and lower bounding approaches for the most efficient formulation. (C) 2010 Elsevier B.V. All rights reserved.

1st International Conference on Engineering and Applied Sciences Optimization, OPT-i 2014 -- 4 June 2014 through 6 June 2014, A online social network consists of individuals or entities which are tied by a certain type of interdependency such as collaboration, friendship or acquaintance. Due to the wide usage of internet, many companies actively use this new media in their marketing campaigns. Given an online social network, a person that influences his/her connections is called an influential. Since companies have limited budgets for advertising, they have to correctly select the influentials, which will forward their message to their connections over various online social networks and hope that a cascade will be triggered so that a maximum number of individuals are reached. In most of the previous studies the social networks are modeled as stochastic fields where the cascading process is represented by linear threshold or independent cascade models. It is shown that determining the top-k influential nodes within the network under this setting is NP-hard and a greedy based heuristic provides a provable approximation guarantee. Following these initial efforts many researchers worked on the improvement of the efficiency of the greedy algorithm without focusing on the solution quality. In this study, the problem of selecting the best k-influentials in social netrowk is studied from the solution quality perspective and using a Variable Neighbourhood Serach(VNS) heuristic optimal solutions are sought. Experimental analysis on certain real-life data is carried out to determine the performance of the techniques proposed.

Arena;Boeing;et al.;FedEx Ground;The Ergonomics Center of North Carolina;The Hershey Company, IIE Annual Conference and Expo 2013 -- 18 May 2013 through 22 May 2013 -- San Juan, In the era of social networks, many companies shift their marketing campaigns to this new media. Any person who influences his/her connections is called an influential. Since companies have limited budgets for advertising, they have to correctly select the influentials, which will forward their message to their connections over the online social network. In this study, the problem of selecting the best influentials regarding different objectives and constraints are modeled. The influential selection problem can be modeled similar to the famous set covering problem. We propose a binary integer programming formulation to represent the influential selection problem. We propose various different solution techniques to obtain close-to-optimal solutions and carry out experimental analysis to determine the performance of the techniques proposed.

The point coverage, sink location, and data routing problems are considered in an integrated way and two new mixed-integer programming formulations are proposed. As these models are difficult to solve, a nested solution procedure is proposed. The best sensor locations are sought by tabu search in the upper level. For the fixed sensor locations, the remaining problem of determining sink locations and data routes are solved efficiently in the lower level. According to the experimental results performed on a number of test instances, the performance of the nested solution approach is quite satisfactory, and the proposed heuristic method brings considerable improvements over a two-stage solution approach.

In this work point coverage, sink location and data routing problems are considered in an integrated way and two new mixed integer programming formulations are proposed. Since these models are computationally difficult to solve, a hierarchical solution procedure is proposed. In the top level, best sensor locations are sought by variable neighbourhood search. Given the sensor locations, a simpler formulation can be obtained and a Lagrangean Heuristic is used to solve the sink location and data routing model efficiently. Experimental results indicate that the performance of hierarchical solution approach is very good.

In this work we consider routing and sink location problems in sensor networks and propose two new mixed integer programming formulations to determine optimal sink locations and data flow routes. The models basically differ in the formulations of their objective functions. We assume that the sensor field consists of a finite set of points, and sensors, which are located on a subset, cover the points of the field completely. Experimental results indicate that these new formulations are very efficient and optimal solutions can be computed easily even for large networks. We also propose Lagrangean relaxation methods to solve the formulations approximately.

Coverage is a fundamental task in sensor networks. We present two binary integer programming models for the effective sensor placement on a grid-structured sensor field when there are more than one type of available sensors with varying sensing quality and price. The first model assumes perfect sensor detection. The second one is more realistic and gives an optimal placement strategy for probabilistic sensing. Both models suffer from the intractability of the binary integer programming formulations. We therefore suggest greedy and Lagrangean heuristics, which are both accurate and efficient. Computational results are also provided.