Page 55 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 55
Test Cases our problems. We reduced the search space with different
method to reach the required accuracy, and to accelerate our
In many test cases we investigated the main behavior of al- process. In the end we compared the results. In the future
gorithms. We worked with about hundred graphs, which we would like to build an efficient simulate annealing frame-
came from a word-association case study. In this graphs the work, then we will test our method on real graphs with real
vertices are words, and the directed connections are associa- churn value from databases of companies.
tion one of words to another. We also used graph generator
(Forest Fire Model) to obtain graphs. [1] The vertex num- Although during the work a lot of theoretical compositions
ber in these graphs is from hundred to thousand. The rate and methods have been introduced, but they have a rele-
of those vertices where the uplift probability is greater than vant role to play in everyday life. Nowadays the informa-
input probability is 25%. For other vertices the rate is 50%. tion spreading and viral marketing are becoming more and
In the first case, the increase of probabilities can be up to more common terms. Economic agents realized that finding
20%, at the other case, the decrease of probabilities can be the relevant customers in connection with the given problem
up to 60%. The other parameters can be seen on the next means financial potential. Solving such questions precisely
table. and quickly can give unexpected positive results.
Table 1: Parameterization 7. ACKNOWLEDGEMENT
variable value I would like to express my gratitude to Dr. Miklo´s Kr´esz,
my supervisor for his enthusiastic encouragement and useful
p(u, v) 0, 1 remarks of this research work.
|V | 100, .., 1000 This research was supported by National Research, Develop-
ment and Innovation Office - NKFIH Fund No. SNN-117879.
wv [0, 1]withunif ormdistribution
k |V |·0, 05 8. REFERENCES
5.3 Results [1] P. Bak, K. Chen, and C. Tang. A forest-fire model and
some thoughts on turbulence. Physics letters A,
After the infection model was built we used simulations on 147(5):297–300, 1990.
our networks to evaluate them. We used it the whole so-
lution space of the given network. Then, we applied our [2] A. Bo´ta, M. Kr´esz, and A. Pluha´r. Approximations of
analytic formula (AF) heuristic with parameter t ≤ 5 for the generalized cascade model. Acta Cybernetica,
the same networks, but we reduced the solution space help- 21(1):37–51, 2013.
ing with the introduced reduction method. We investigate
the average of results. If we use this heuristic, we need to [3] W. Chen, C. Wang, and Y. Wang. Scalable influence
be careful about the parameters, because the accuracy will maximization for prevalent viral marketing in
be at the expense of efficiency. We need to find the balance. large-scale social networks. In KDD, 2010.
Table 2: Results of positive problem testing [4] P. Domingos and M. Richardson. Mining the network
value of customers. In Proceedings of the Seventh
method rate ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’01,
whole solution space with Simulation 100% pages 57–66, New York, NY, USA, 2001. ACM.
degree reduction with AF 95,51% [5] M. Granovetter. Threshold models of collective
behavior. American Journal of Sociology,
modif ied degree reduction with AF 96, 00% 83(6):1420–1443, 1978.
Table 3: Results of negative problem testing [6] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing
the spread of influence through a social network. In
method rate Proceedings of the Ninth ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining,
whole solution space with Simulation 100% KDD ’03, pages 137–146, New York, NY, USA, 2003.
ACM.
degree reduction with AF 89,52%
[7] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing
modif ied degree reduction with AF 99, 14% the spread of influence through a social network.
Theory of Computing, 11(4):105–147, 2015.
When we used the reduction, the run time was five times
faster on average than the case of whole solution space. The [8] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An
tables show results obtained from the mean value of different analysis of approximations for maximizing submodular
networks. At the negative problem testing the values are set functions—i. Mathematical Programming,
smaller than at the positive case because of the theoretical 14(1):265–294, 1978.
background. At this point the difference is greater then at
positive, but the behavior of tasks are similar. The network [9] A. Srivastava, C. Chelmis, and V. K. Prasanna. The
effect works in a different way from network which negative- unified model of social influence and its application in
parameterized than a positive one and it can be detected influence maximization. Social Network Analysis and
in. Mining, 5(1):1–15, 2015.
6. CONCLUTIONS AND FUTURE WORKS [10] D. B. West. Introduction to Graph Theory. Prentice
Hall, 2005.
During our work we defined several problems for the influence-
maximization in generalized models. We worked on suit-
able greedy framework, which gave guarantee precision for
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 55
Ljubljana, Slovenia, 12 October
method to reach the required accuracy, and to accelerate our
In many test cases we investigated the main behavior of al- process. In the end we compared the results. In the future
gorithms. We worked with about hundred graphs, which we would like to build an efficient simulate annealing frame-
came from a word-association case study. In this graphs the work, then we will test our method on real graphs with real
vertices are words, and the directed connections are associa- churn value from databases of companies.
tion one of words to another. We also used graph generator
(Forest Fire Model) to obtain graphs. [1] The vertex num- Although during the work a lot of theoretical compositions
ber in these graphs is from hundred to thousand. The rate and methods have been introduced, but they have a rele-
of those vertices where the uplift probability is greater than vant role to play in everyday life. Nowadays the informa-
input probability is 25%. For other vertices the rate is 50%. tion spreading and viral marketing are becoming more and
In the first case, the increase of probabilities can be up to more common terms. Economic agents realized that finding
20%, at the other case, the decrease of probabilities can be the relevant customers in connection with the given problem
up to 60%. The other parameters can be seen on the next means financial potential. Solving such questions precisely
table. and quickly can give unexpected positive results.
Table 1: Parameterization 7. ACKNOWLEDGEMENT
variable value I would like to express my gratitude to Dr. Miklo´s Kr´esz,
my supervisor for his enthusiastic encouragement and useful
p(u, v) 0, 1 remarks of this research work.
|V | 100, .., 1000 This research was supported by National Research, Develop-
ment and Innovation Office - NKFIH Fund No. SNN-117879.
wv [0, 1]withunif ormdistribution
k |V |·0, 05 8. REFERENCES
5.3 Results [1] P. Bak, K. Chen, and C. Tang. A forest-fire model and
some thoughts on turbulence. Physics letters A,
After the infection model was built we used simulations on 147(5):297–300, 1990.
our networks to evaluate them. We used it the whole so-
lution space of the given network. Then, we applied our [2] A. Bo´ta, M. Kr´esz, and A. Pluha´r. Approximations of
analytic formula (AF) heuristic with parameter t ≤ 5 for the generalized cascade model. Acta Cybernetica,
the same networks, but we reduced the solution space help- 21(1):37–51, 2013.
ing with the introduced reduction method. We investigate
the average of results. If we use this heuristic, we need to [3] W. Chen, C. Wang, and Y. Wang. Scalable influence
be careful about the parameters, because the accuracy will maximization for prevalent viral marketing in
be at the expense of efficiency. We need to find the balance. large-scale social networks. In KDD, 2010.
Table 2: Results of positive problem testing [4] P. Domingos and M. Richardson. Mining the network
value of customers. In Proceedings of the Seventh
method rate ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’01,
whole solution space with Simulation 100% pages 57–66, New York, NY, USA, 2001. ACM.
degree reduction with AF 95,51% [5] M. Granovetter. Threshold models of collective
behavior. American Journal of Sociology,
modif ied degree reduction with AF 96, 00% 83(6):1420–1443, 1978.
Table 3: Results of negative problem testing [6] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing
the spread of influence through a social network. In
method rate Proceedings of the Ninth ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining,
whole solution space with Simulation 100% KDD ’03, pages 137–146, New York, NY, USA, 2003.
ACM.
degree reduction with AF 89,52%
[7] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing
modif ied degree reduction with AF 99, 14% the spread of influence through a social network.
Theory of Computing, 11(4):105–147, 2015.
When we used the reduction, the run time was five times
faster on average than the case of whole solution space. The [8] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An
tables show results obtained from the mean value of different analysis of approximations for maximizing submodular
networks. At the negative problem testing the values are set functions—i. Mathematical Programming,
smaller than at the positive case because of the theoretical 14(1):265–294, 1978.
background. At this point the difference is greater then at
positive, but the behavior of tasks are similar. The network [9] A. Srivastava, C. Chelmis, and V. K. Prasanna. The
effect works in a different way from network which negative- unified model of social influence and its application in
parameterized than a positive one and it can be detected influence maximization. Social Network Analysis and
in. Mining, 5(1):1–15, 2015.
6. CONCLUTIONS AND FUTURE WORKS [10] D. B. West. Introduction to Graph Theory. Prentice
Hall, 2005.
During our work we defined several problems for the influence-
maximization in generalized models. We worked on suit-
able greedy framework, which gave guarantee precision for
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 55
Ljubljana, Slovenia, 12 October
