alphacore

АльфаКор

Это дополнительные файлы к документу AlphaCore KDD.

Использование

Пока это не упаковано, сохраните файл алгоритмы/alphaCore.R.

Получите граф с именованными вершинами и весами ребер:

 g <- erdos.renyi.game(200, 2/200, directed = T)
E(g)$weight <- 1:ecount(g)
V(g)$name <- paste("v", 1:vcount(g), sep="")

Запустите AlphaCore с параметрами по умолчанию.

 > alphaCore(g)
     node     alpha batch
  1:   v1 0.3281309    19
  2:   v2 0.3281309    30
  3:   v3 0.3724843    34
  4:   v4 0.3281309    23
  5:   v5 0.3281309    19
 ---                     
196: v196 0.3281309    28
197: v197 0.0000000     1
198: v198 0.3724843    34
199: v199 0.3281309    23
200: v200 0.3281309    23

Запустите AlphaCore со встроенными функциями свойств границ.

 > alphaCore(g, featureComputeFun = customNodeFeatures(c("indegree", "triangles")))
     node     alpha batch
  1:   v1 0.3060040    14
  2:   v2 0.0000000     6
  3:   v3 0.0000000     5
  4:   v4 0.0000000     5
  5:   v5 0.0000000     6
 ---                     
196: v196 0.6381691    19
197: v197 0.0000000     5
198: v198 0.0000000     5
199: v199 0.6381691    19
200: v200 0.0000000     8

Пример реализации Python (предоставлен Джейсоном Чжу!):

 > import networkx as nx
> G = nx.erdos_renyi_graph(n=200, seed=1, p=2/200, directed=True)
> for idx, (u,v,w) in enumerate(G.edges(data=True)):
      w['value'] = idx

> alphaCore(G)
   nodeID 	alpha   batchID
0 	    18 	  0.0         0
1 	    75 	  0.0 	     0
2 	    78 	  0.0 	     0
3 	    25 	  0.3 	     5
4 	    91 	  0.3 	     5
... 	... 	  ... 	   ...
195 	  8 	  0.7 	    27
196 	131 	  0.7 	    27
197 	185 	  0.7 	    27
198 	192 	  0.7 	    27
199 	158 	  0.7 	    28

Оценка

Для запуска вам сначала необходимо загрузить три набора данных:

Токен-сети (11,4 ГБ)

Файлы размещены по адресу: https://zenodo.org/record/4898412. Сохраните файл Transfers.db в data/tokens/transfers.db. Соответствующий файл ExchangeLabels.csv следует поместить в data/tokens/exchangeLabels.csv.

Реддит перекрестные ссылки

Перекрестные ссылки Reddit являются частью http://snap.stanford.edu/conflict/conflict_data.zip. В zip-файле их можно найти в /prediction/detailed_data/. Поместите файл в папку data/reddit/post_crosslinks_info.tsv.

Маршруты полетов

Получите этот файл с http://opsahl.co.uk/tnet/datasets/openflights.txt и сохраните его в data/flights/openflights.txt.

Запуск оценки

Откройте файл Assessment.R из основного каталога.

Это основной файл для запуска оценки. Введите количество ядер ЦП и путь к извлеченному файлу базы данных.

Чтобы выполнить всю оценку, в идеале делайте это на сервере с Rscript, поскольку некоторые алгоритмы, то есть некоторые центральности, зависящие от вычислений кратчайшего пути для всех пар, и наша собственная реализация взвешенного k-ядра имеют очень долгое время работы. Полное выполнение занимает от 1 до 3 дней, в зависимости от оборудования.

Однако AlphaCore с экспоненциально убывающим размером шага работает довольно быстро, хотя это всего лишь реализация R.

Цитирование

Пожалуйста, используйте следующую запись BibTeX:

 @inproceedings{10.1145/3447548.3467322,
author = {Victor, Friedhelm and Akcora, Cuneyt G. and Gel, Yulia R. and Kantarcioglu, Murat},
title = {Alphacore: Data Depth Based Core Decomposition},
year = {2021},
isbn = {9781450383325},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447548.3467322},
doi = {10.1145/3447548.3467322},
booktitle = {Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining},
pages = {1625–1633},
numpages = {9},
keywords = {core decomposition, networks, data depth},
location = {Virtual Event, Singapore},
series = {KDD '21}
}