Preview

Труды Института системного программирования РАН

Расширенный поиск

Некоторые задачи на графовых базах данных

https://doi.org/10.15514/ISPRAS-2016-28(4)-12

Полный текст:

Аннотация

Одним из наиболее популярных и актуальных подвидов нереляционных баз данных являются графовые базы данных. В данной работе рассмотрены задачи на таких базах данных, которые наиболее часто встречаются в современной литературе. Изучены задачи максимизации влияния, motif mining (MM), задача оценки схожести узлов графа, сопоставление образца в графе. Рассмотрены первичные алгоритмы каждого направления и некоторые промежуточные работы. Проанализированы алгоритмы, соответствующие текущему положению дел.

Об авторе

Р. И. Гуральник
Санкт-Петербургский государственный университет
Россия


Список литературы

1. Pettey C., Goasduff L. (2011) Gartner, Inc. Gartner Says Solving 'Big Data' Challenge Involves More Than Just Managing Volumes of Data (online publication). Available at: http://www.gartner.com/newsroom/id/1731916, accessed 07.08.2016

2. DIS Group, (2014) “Big data.” http://www.dis group.ru/solutions/data_

3. management/big_data/, accessed 07.08.2016.

4. Бартенев М., Вишняков И . “Использование графовых баз данных в целях оптимизации анализа биллинговой информации,” Инженерный журнал: наука и инновации, no. 11, 2013.

5. Manyika J., Chui M., Brown B., Bughin J., Dobbs R., Roxburgh C., Byers A. H . “Big data: The next frontier for innovation, competition, productivity,” 2011.

6. Jeh G., Widom J . “Simrank: a measure of structural-context similarity,” in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 538–543, ACM, 2002.

7. Fogaras D. and R´acz B . “Scaling link-based similarity search,” in Proceedings of the 14th international conference on World Wide Web, pp. 641–650, ACM, 2005.

8. He G., Feng H., Li C., Chen H . “Parallel simrank computation on large graphs with iterative aggregation,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 543–552, ACM, 2010.

9. Li C., Han J., He G., Jin X., Sun Y., Yu Y., Wu T . “Fast computation of simrank for static and dynamic information networks,” in Proceedings of the 13th International Conference on Extending Database Technology, pp. 465–476, ACM, 2010.

10. Li P., Liu H., Yu J. X., He J., Du X . “Fast single-pair simrank computation.,” in SDM, pp. 571–582, SIAM, 2010.

11. Yu W., Lin X., Le J . “Taming computational complexity: Efficient and parallel simrank optimizations on undirected graphs,” in International Conference on Web-Age Information Management, pp. 280–296, Springer, 2010.

12. Lizorkin D., Velikhov P., Grinev M., Turdakov D . “Accuracy estimate and optimization techniques for simrank computation,” The VLDB Journal The International Journal on Very Large Data Bases, vol. 19, no. 1, pp. 45–66, 2010.

13. Yu W., Lin X., Zhang W., Chang L., Pei J . “More is simpler: Effectively and efficiently assessing node-pair similarities based on hyperlinks,” Proceedings of the VLDB Endowment, vol. 7, no. 1, pp. 13–24, 2013.

14. Yu W., Zhang W., Lin X., Zhang Q., Le J . “A space and time efficient algorithm for simrank computation,” World Wide Web, vol. 15, no. 3, pp. 327–353, 2012

15. Maehara T., Kusumoto M., Kawarabayashi K.-i . “Scalable simrank join algorithm,” in 2015 IEEE 31st International Conference on Data Engineering, pp. 603–614, IEEE, 2015.

16. Fujiwara Y., Nakatsuji M., Shiokawa H., Onizuka M . “Efficient search algorithm for simrank,” in Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 589–600, IEEE, 2013.

17. Zhu R., Zou Z., Li J . “Simrank computation on uncertain graphs,” in 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 565–576, May 2016.

18. Domingos P., Richardson M . “Mining the network value of customers,” in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57–66, ACM, 2001.´

19. Kempe D., Kleinberg J., Tardos E . “Maximizing the spread of influence through a social network,” in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137–146, ACM, 2003.

20. Chen W., Wang C., Wang Y . “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1029–1038, ACM, 2010.

21. Goyal A., Bonchi F., L. Lakshmanan V . “A data-based approach to social influence maximization,” Proceedings of the VLDB Endowment, vol. 5, no. 1, pp. 73– 84, 2011.

22. Jung K., Heo W., Chen W . “Irie: Scalable and robust influence maximization in social networks,” in 2012 IEEE 12th International Conference on Data Mining, pp. 918–923, IEEE, 2012.

23. Kim J., Kim S.-K., Yu H . “Scalable and parallelizable processing of influence maximization for large-scale social networks?,” in Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 266–277, IEEE, 2013.

24. Kim D., Lee J.-G., Lee B. S . “,”

25. Li G., Chen S., Feng J., Tan K.-l., Li W.-s . “Efficient location-aware influence maximization,” in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 87–98, ACM, 2014.

26. Wang X., Zhang Y., Zhang W., Lin X . “Distance-aware influence maximization in geo-social network,”

27. Khan A., Zehnder B., Kossmann D . “Revenue maximization by viral marketing: A social network host’s perspective.”

28. Li H., Bhowmick S. S., Cui J., Gao Y., Ma J . “Getreal: Towards realistic selection of influence maximization strategies in competitive networks,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1525– 1537, ACM, 2015.

29. Borgs C., Brautbar M., Chayes J., Lucier B . “Maximizing social influence in nearly optimal time,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 946–957, Society for Industrial and Applied Mathematics, 2014.

30. Tang Y., Xiao X., Shi Y . “Influence maximization: Near-optimal time complexity meets practical efficiency,” in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 75–86, ACM, 2014.

31. Mahdian M., Ye Y., Zhang J . “Improved approximation algorithms for metric facility location problems,” in International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229–242, Springer, 2002.

32. Gallagher B . “Matching structure and semantics: A survey on graph-based pattern matching,” AAAI FS, vol. 6, pp. 45–53, 2006.

33. Giugno R., Shasha D . “Graphgrep: A fast and universal method for querying graphs,” in Pattern Recognition, 2002. Proceedings. 16th International Conference on, vol. 2, pp. 112–115, IEEE, 2002.

34. Natarajan M . “Understanding the structure of a drug traffcking organization: a conversational analysis,” Crime Prevention Studies, vol. 11, pp. 273–298, 2000.

35. Fan W., Li J., Ma S., Tang N., Wu Y., Wu Y . “Graph pattern matching: From intractable to polynomial time,” Proc. VLDB Endow., vol. 3, pp. 264–275, Sept. 2010.

36. Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U . “Network motifs: simple building blocks of complex networks,” Science, vol. 298, no. 5594, pp. 824–827, 2002.

37. Kashtan N., Itzkovitz S., Milo R., Alon U . “Mfinder tool guide,” Department of Molecular Cell Biology and Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot Israel, Tech Rep, 2002.

38. Wernicke S., Rasche F . “Fanmod: a tool for fast network motif detection,” Bioinformatics, vol. 22, no. 9, pp. 1152–1153, 2006.

39. Grochow J. A., Kellis M . “Network motif discovery using subgraph enumeration and symmetry-breaking,” in Annual International Conference on Research in Computational Molecular Biology, pp. 92–106, Springer, 2007.

40. Schreiber F., Schwobbermeyer H . “Frequency concepts and pattern detection for the analysis of motifs in networks,” in Transactions on computational systems biology III, pp. 89–104, Springer, 2005.

41. Omidi S., Schreiber F., Masoudi-Nejad A . “Moda: an efficient algorithm for network motif discovery in biological networks,” Genes & genetic systems, vol. 84, no. 5, pp. 385–395, 2009.

42. Ribeiro P., Silva F . “G-tries: an efficient data structure for discovering network motifs,” in Proceedings of the 2010 ACM Symposium on Applied Computing, pp. 1559–1566, ACM, 2010.

43. Gurukar S., Ranu S., Ravindran B . “Commit: A scalable approach to mining communication motifs from dynamic networks,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 475–489, ACM, 2015.


Для цитирования:


Гуральник Р.И. Некоторые задачи на графовых базах данных. Труды Института системного программирования РАН. 2016;28(4):193-216. https://doi.org/10.15514/ISPRAS-2016-28(4)-12

For citation:


Guralnik R.I. Some problems on graph databases. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(4):193-216. (In Russ.) https://doi.org/10.15514/ISPRAS-2016-28(4)-12

Просмотров: 117


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)