Readme.md

   1 ## Description
   2
   3 A phylomemetic network (or phylomemy) is an adaptation
   4 of the concept of the phylogenetic tree,
   5 combined with Richard Dawkins' intuition of a meme,
   6 to describe the complex dynamic structure of transformation of relations between terms.
   7
   8 This package is a partial implementation of some
   9 noteworthy algorithms composed to compute a phylomemy,
  10 in order to understand and test them.
  11
  12 ## Clustering
  13
  14 ### Linear time Closed itemset Miner (LCM)
  15
  16 Based upon:
  17 -  « HLCM: a first experiment on parallel data mining with Haskell ».
  18    By Alexandre Termier &amp; Benjamin Négrevergne &amp; Simon Marlow &amp; Satnam Singh
  19    <https://lig-membres.imag.fr/termier/HLCM/hlcm.pdf>
  20    From the original LCM algorithm from Takaki Uno and Hiroki Arimura.
  21    <http://osdm.uantwerpen.be/papers/p77-uno.pdf>
  22
  23 ### Maximal clique
  24 TODO
  25
  26 ## Temporal matching
  27
  28 #### Maximal spanning forest
  29
  30 > If the order in which edges will be deleted is known ahead of time, then we
  31 > can solve the dynamic connectivity problem in time `O(log n)` per query. If
  32 > we can maintain a maximum spanning forest where edges are ordered by their
  33 > deletion time, we know that when we delete some edge that is in the forest,
  34 > there is no possible edge that can replace it. If there were some edge that
  35 > connects the same two components the deleted edge does, then this other edge
  36 > would have been part of the maximum spanning forest instead of the edge we
  37 > deleted. This makes the delete operation trivial: we simply need to split the
  38 > tree into its two parts if the edge to delete is part of our forest, or
  39 > ignore the operation otherwise.
  40 https://en.wikipedia.org/wiki/Dynamic_connectivity#Offline_dynamic_connectivity
  41
  42 ## Acknowledgements
  43
  44 Based upon:
  45
  46 - Chavalarias D &amp; Cointet J-P (2013).
  47   « Phylomemetic Patterns in Science Evolution—The Rise and Fall of Scientific Fields ».
  48   PLoS ONE 8(2): e54847. <https://doi.org/10.1371/journal.pone.0054847>
  49
  50 - Chavalarias, D. &amp; Lobbé, Q. &amp; Delanoë, A. (2021).
  51   « Draw me Science: Multi-level and multi-scale reconstruction of knowledge dynamics with phylomemies ».
  52   Scientometrics. <https://doi.org/10.1007/s11192-021-04186-5>