Streaming Graph Server with partitioning
This repository contains the slightly modified version of Fennel, and Linear Deterministic Greedy (LDG) partitioning algorithms to work with stream of edges (a pair of vertices).
The only difference is , Practitioner accept edge of a graph instead of single vertexes and add both vertexes(aka Nodes) to partitions.
I have develp this code for testing out different streaming graph partitioning algorithms, and validate and try out the partioninig quality with visualization.
Partitioning algorithms are implemented in cpp+11 and visualization is done using Cytoscape.js. Use Apache Kafka for consume stream of edges in a graph.
A python script is used for streaming edges from a graph in a file. It can also stream a graph by taking user inputs from the terminal.
Practitioner accept the graph as a stream of edges , where edge contains a space separated vertex pair, i:e 22 45
This tool uses cmake for managing package versions and building the binaries. CMake 3.10 or latest version is required to build the tool.
Moreover following packages are being used for the purpose mentioned below. You need to install them seperatly.
SQLite3 (https://www.sqlite.org/download.html)
sqlite-autoconf-3390200 from this URL.sqlite-autoconf-3390200.tar.gz to some location. E.g., /media/user/software/sqlite-autoconf-3390200-install./configure --prefix=/media/user/software/sqlite-autoconf-3390200target_link_libraries path to libsqlite3.target_link_libraries(JasmineGraph /media/user/software/sqlite-autoconf-3390200/lib/libsqlite3.so)cppkafka (https://github.com/mfontanini/cppkafka)
sudo apt install librdkafka-devsudo apt-get install libboost-all-devcmake <OPTIONS> .. use of cmake .. should be sufficient enoughsudo make install from the build directorySpdLog (https://github.com/gabime/spdlog)
SQLite3 (https://www.sqlite.org/download.html)
sqlite-autoconf-3390200 from this URL.sqlite-autoconf-3390200.tar.gz to some location. E.g., /media/user/software/sqlite-autoconf-3390200-install./configure --prefix=/media/user/software/sqlite-autoconf-3390200target_link_libraries path to libsqlite3.target_link_libraries(JasmineGraph /media/user/software/sqlite-autoconf-3390200/lib/libsqlite3.so)SQLite3 (https://www.sqlite.org/download.html)
sqlite-autoconf-3390200 from this URL.sqlite-autoconf-3390200.tar.gz to some location. E.g., /media/user/software/sqlite-autoconf-3390200-install./configure --prefix=/media/user/software/sqlite-autoconf-3390200target_link_libraries path to libsqlite3.target_link_libraries(JasmineGraph /media/user/software/sqlite-autoconf-3390200/lib/libsqlite3.so)SQLite3 (https://www.sqlite.org/download.html)
sqlite-autoconf-3390200 from this URL.sqlite-autoconf-3390200.tar.gz to some location. E.g., /media/user/software/sqlite-autoconf-3390200-install./configure --prefix=/media/user/software/sqlite-autoconf-3390200target_link_libraries path to libsqlite3.target_link_libraries(JasmineGraph /media/user/software/sqlite-autoconf-3390200/lib/libsqlite3.so)SQLite3 (https://www.sqlite.org/download.html)
sqlite-autoconf-3390200 from this URL.sqlite-autoconf-3390200.tar.gz to some location. E.g., /media/user/software/sqlite-autoconf-3390200-install./configure --prefix=/media/user/software/sqlite-autoconf-3390200target_link_libraries path to libsqlite3.target_link_libraries(JasmineGraph /media/user/software/sqlite-autoconf-3390200/lib/libsqlite3.so)This was implemented as a part of adding new streaming graph partitioning algorithm to Jasmine Graph server. You could try out Jasmine graph server for more robust work on graph partitioning and analysis.
I have used following maximization formulae for deriving the partition index for most optimum partitioning. The hubristic used in here is, if a vertex having more neighbors and have not reached to it’s maximum capacity, Then it(Partition) will have most likelihood to accept that vertex.
Inter partition cost
Intra partition cost
***Received the end of stream0 => Vertext count = 22370 => Edges count = 11250 => Edge cuts count = 4400 => Cut ratio = 0.281151 => Vertext count = 22351 => Edges count = 11621 => Edge cuts count = 4301 => Cut ratio = 0.2701012 => Vertext count = 22362 => Edges count = 11562 => Edge cuts count = 4472 => Cut ratio = 0.2788523 => Vertext count = 22363 => Edges count = 11533 => Edge cuts count = 4553 => Cut ratio = 0.28296Time taken = 3.88941e+07 micro seconds
***Received the end of stream0 => Vertext count = 17110 => Edges count = 6880 => Edge cuts count = 17580 => Cut ratio = 0.7187241 => Vertext count = 17111 => Edges count = 5801 => Edge cuts count = 19001 => Cut ratio = 0.7661292 => Vertext count = 17102 => Edges count = 5532 => Edge cuts count = 19732 => Cut ratio = 0.7810773 => Vertext count = 17113 => Edges count = 5453 => Edge cuts count = 19613 => Cut ratio = 0.782522Time taken = 5.8881e+07 micro seconds
***Received the end of stream0 => Vertext count = 16440 => Edges count = 3230 => Edge cuts count = 26010 => Cut ratio = 0.8895351 => Vertext count = 16951 => Edges count = 3101 => Edge cuts count = 26441 => Cut ratio = 0.8950582 => Vertext count = 16722 => Edges count = 3062 => Edge cuts count = 26482 => Cut ratio = 0.8964123 => Vertext count = 16463 => Edges count = 3263 => Edge cuts count = 25353 => Cut ratio = 0.886054Time taken = 428249 micro seconds
***Received the end of stream0 => Vertext count = 50 => Edges count = 40 => Edge cuts count = 40 => Cut ratio = 0.5Printing edge cuts of 0 partition8 ____| ---> 939 ____| ---> 3614 ____| ---> 1735 ____| ---> 34Printing edge list of 0 partition6 ____| ===> 87 ____| ===> 814 ____| ===> 16| ===> 291 => Vertext count = 51 => Edges count = 31 => Edge cuts count = 61 => Cut ratio = 0.666667Printing edge cuts of 1 partition9 ____| ---> 836 ____| ---> 3919 ____| ---> 2036 ____| ---> 3714 ____| ---> 1336 ____| ---> 38Printing edge list of 1 partition18 ____| ===> 1935 ____| ===> 3641 ____| ===> 422 => Vertext count = 42 => Edges count = 12 => Edge cuts count = 32 => Cut ratio = 0.75Printing edge cuts of 2 partition20 ____| ---> 1937 ____| ---> 3615 ____| ---> 13Printing edge list of 2 partition9 ____| ===> 103 => Vertext count = 4.53 => Edges count = 33 => Edge cuts count = 53 => Cut ratio = 0.625Printing edge cuts of 3 partition17 ____| ---> 1434 ____| ---> 3513 ____| ---> 1438 ____| ---> 3613 ____| ---> 15Printing edge list of 3 partition5 ____| ===> 1312 ____| ===> 1333 ____| ===> 34Time taken = 28433 micro seconds