In this paper we present a summary of our work which has led to the conception of a new model for the fast construction of proximity graphs. We present the state of the art in graph self-assembly, and then we detail the self-assembly behavior observed in real ants from which our model is derived. We describe our main algorithm, called AntGraph, where each ant represents one datum and where the proximity graph is built in an incremental way. Ants perform two steps: following the path of maximum local similarity, and then connecting to other ants. We present a hierarchical extension, called H-AntGraph, which can build large graphs (with up to 1 million data items). We study the properties of the constructed graphs, and compare our results with those obtained by other methods. We use force-directed graph layout algorithms to display the graphs and to allow the domain expert to perform an interactive clustering task. We validate this approach with a comparative user-study.
AbrahamA.RamosV. (2003, 08-12December). Web usage mining using artificial ant colony clustering and linear genetic programming. In the congress on evolutionary computation (p. 1384–1391). Canberra, Australia: IEEE-Press.
2.
AdlemanL. M. (1994, November). Molecular computation of solutions to combinatorial problems. Science, 266(5187), 1021–1024.
3.
AmosM. (2005). Theoretical and experimental dna computation (Vols. XIII, 173 pages). Springer Verlag Berlin, Heidelberg.
4.
AndersonC.TheraulazG.DeneubourgJ. L. (2002, May1). Self-assemblages in insect societies. Insectes Sociaux, 49(2), 99–110.
5.
AngelovS.KhannaS.VisontaiM. (2006). On the complexity of graph self-assembly in accretive systems. In MaoC.YokomoriT. (Eds.), Dna (Vol. 4287, p. 95–110). Springer.
6.
AzzagH.VenturiniG.OliverA.GuinotC. (2007). A hierarchical ant based clustering algorithm and its use in three real-world applications. European Journal of Operational Research, 179(3), 906–922.
7.
BayS. D.KiblerD. F.PazzaniM. J.SmythP. (2000). The UCI KDD archive of large data sets for data mining research and experimentation. SIGKDD Explorations, 2(2), 81–85.
8.
BlakeC.MerzC. (1998). UCI repository of machine learning databases.
9.
BoleyD.GiniM.HastingsK.MobasherB.MooreJ. (1998). A client-side agent for document categorization and exploration. In (Vol. 8, p. 387–399). Journal of Internet Research.
10.
BoseP.DujmovicV.HurtadoF.IaconoJ.LangermanS.MeijerH.. (2012). Proximitygraphs: E, δ, Δ, χ and ω. In Proceedings of the 28th european workshop on computational geometry (eurocg12).
11.
CamazineS.FranksN. R.SneydJ.BonabeauE.DeneubourgJ.-L.TheraulaG. (2001). Self-organization in biological systems. Princeton, NJ, USA: Princeton University Press.
12.
CignoniP.MontaniC.ScopignoR. (1998). Dewall: A fast divide and conquer Delaunay triangulation algorithm in ed. Computer-Aided Design, 30(5), 333–341.
13.
Da CostaD.VenturiniG. (2007). A visual and interactive data exploration method for large data sets and clustering. In Adma ’07: Proceedings of the 3rd international conference on advanced data mining and applications (pp. 553–561). Berlin, Heidelberg: Springer-Verlag.
14.
DanosV.TarissanF. (2005). Self assembling graphs. In MiraJ.ÁlvarezJ. R. (Eds.), Iwinac (1) (Vol. 3561, p. 498–507). Springer.
15.
DanosV.TarissanF. (2007). Self-assembling graphs. Natural Computing: an international journal, 6(3), 339–358.
16.
DeneubourgJ.-L.GossS.FranksN.Sendova-FranksA.DetrainC.ChretienL. (1990).The dynamics of collective sorting: robot-like ant and ant-like robots. In Proceedings of thefirst international conference on simulation of adaptive behavior (pp. 356–365).
17.
Di BattistaG.EadesP.TamassiaR.TollisI. G. (1998). Graph drawing: Algorithms for the visualization of graphs. Upper Saddle River, NJ, USA: Prentice Hall PTR.
18.
DorigoM.TrianniV.ŞahinE.GroβR.LabellaT. H.BaldassarreG.. (2004, September). Evolving self-organizing behaviors for a swarm-bot. Auton. Robots, 17 (2–3), 223–245.
19.
EadesP. (1984). A heuristic for graph drawing. In Congressus numeranium (Vol. 42, p. 140–160).
20.
EsterM.KriegelH.-P.SanderJ. (1997). Spatial data mining: A database approach. In Proceedings of the 5th int. symposium on large spatial databases (ssd ’97) (pp. 47-66).
21.
FrickA.LudwigA.MehldauH. (1995). A fast adaptive layout algorithm for undirected graphs. In Proceedings of the dimacs international workshop on graph drawing (pp. 388–403). London, UK, UK: Springer-Verlag.
22.
FruchtermanT.ReingoldE. (1991). Graph drawing by force-directed placement. In Software- practice and experience (Vol. 21, p. 1129–1164).
23.
GabrielK. R.SokalR. R. (1969). A new statistical approach to geographic variation analysis.In Systematic zoology (p. 259–278).
24.
GarzonM. H.DeatonR. J.BarnesK. (1999, 13–17July). On self-assembling graphs in vitro. In BanzhafW.. (Eds.), Proceedings of the genetic and evolutionary computation conference (Vol. 2, pp. 1805–1809). Orlando, Florida, USA: Morgan Kaufmann.
25.
GossS.DeneubourgJ.-L. (1991). Harvesting by a group of robots. In VarelaF.BourgineP. (Eds.), Proceedings of the first european conference on artificial life (pp. 195–204). Paris, France: Elsevier Publishing.
26.
GowerJ. C.LegendreP. (1986, March). Metric and euclidean properties of dissimilarity coeficients. Journal of Classification, 3(1), 5–48.
27.
GroβR.DorigoM. (2008). Self-assembly at the macroscopic scale. Proceedings of the IEEE, 96(9), 1490–1508.
28.
GuinotC.MalvyD. J.-M.MorizotF.TenenhausM.LatreilleJ.LopezS.. (2004, December, 22). Classification of healthy human facial skin. CRC Press. (Textbook of Cosmetic Dermatology Third edition)
29.
HacidH.YoshidaT. (2007, May). Incremental neighborhood graphs construction for multidimensional databases indexing. In the canadian artificial intelligence conference, canai 2007, lnai 4509 (pp. 405–416). Montreal, Quebec, Canada.
30.
HandlJ.KnowlesJ.DorigoM. (2003). Design and application of hybrid intelligent systems. In AbrahamA.KöoppenM.FrankeK. (Eds.), (pp. 204–213). Amsterdam, The Netherlands, The Netherlands: IOS Press.
31.
HandlJ.KnowlesJ.DorigoM. (2006, January). Ant-based clustering and topographic mapping. In (Vol. 12, pp. 35–61). Cambridge, MA, USA: MIT Press.
32.
HandlJ.MeyerB. (2007, December). Ant-based and swarm-based clustering. In (Vol. 1, pp. 95–113).
33.
KamadaT.KawaiS. (1989). An algorithm for drawing general undirected graphs. In Information processing letters (Vol. 31, p. 7–15).
34.
KeimD. A.AnkerstM. (2001). Visual data mining and exploration of large databases. In the 5th european conference on principles and practice of knowledge discovery in databases. (Tutorial PKDD 2001)
35.
KrasnogorN.GheorgheM. (2005, April). Systems self-assembly. International Workshop, The Grand Challenge in Non-Classical Computation, 18–19th April 2005, the University of York, United-Kingdom.
36.
KuntzP.LayzellP.SnyersD. (1997). A colony of ant-like agents for partitioning in vlsi technology. In HusbandsP.HarveyI. (Eds.), Proceedings of the fourth european conference on artificial life (pp. 417–424).
37.
KuntzP.SnyersD.LayzellP. J. (1998). A stochastic heuristic for visualising graph clusters in a bi-dimensional space prior to partitioning. J. Heuristics, 5(3), 327–351.
38.
LanceG.WilliamsW. (1967). A general theory of classificatory sorting strategies: I. hierarchical systems. Computer journal, 9(4), 373–380.
39.
LioniA.SauwensC.TheraulazG.DeneubourgJ.-L. (2001). The dynamics of chain formation in oecophylla longinoda. Journal of Insect Behavior, 14, 679–696.
40.
MondadaF.PettinaroG. C.GuignardA.KweeI. W.FloreanoD.DeneubourgJ.-L.. (2004). Swarm-bot: A new distributed robotic concept. Auton. Robots, 17 (2–3), 193–221.
41.
MurataS.KurokawaH.KokajiS. (1994, May). Self-assembling machine. In Ieee international conference on robotics and automation (Vol. 1, p. 441–448). Sans Diego, CA, USA.
42.
PetersonG. L.MayerC. B.KublerT. L. (2008, March). Ant clustering with locally weighted ant perception and diversified memory. Swarm Intelligence, 2(1), 43–68.
43.
PreparataF. P.ShamosM. I. (1985). Computational Geometry: Introduction (Monographs in Computer Science). Springer-Verlag.
44.
RandW. M. (1971). Objective Criteria for the Evaluation of Clustering Methods. Journal of the American Statistical Association, 66(336), 846–850.
45.
ReifJ. H.SahuS.YinP. (2005). Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems. In CarboneA.PierceN. A. (Eds.), Dna (Vol. 3892, p. 257–274). Springer.
46.
SaltonG.BuckleyC. (1988). Term-weighting approaches in automatic text retrieval. Inf. Process. Manage. 24(5), 513–523.
47.
SneathP. H.SokalR. R. (1973). Numerical taxonomy. San FranciscoW.H. Freeman.
48.
TheraulazG.BonabeauE.SauwensC.DeneubourgJ.-L.LioniA.LibertF.. (2001). Model of droplet formation and dynamics in the Argentine ant (Linepithema humile mayr). Bulletin of Mathematical Biology, 63, 1079–1093.
49.
ToussaintG. T.(1980). The relative neighborhood graphs in a finite planar set. In Pattern recognition (261–268).
50.
ToussaintG. T. (1991). Some unsolved problems on proximity graphsSome unsolved problems on proximity graphs. In DearholtD. W.HarraryF. (Eds.), Memoranda in computer and cognitive science MCCS-91-224. Computing research laboratory, New Mexico state University Las Cruces.
51.
TutteW. T. (1963). How to draw a graph. In Proceedings london mathematical society (Vol. 13, p. 743–768). Author
