# ISC-PIF Publications

Item: 12/358
1 10 11 12 13 14 48 358

## View Item

 User sebag title Scaling Analysis of Affinity Propagation Authors Furtlehner, C. , Sebag, M. and Xiangliang, Z. Source Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, Vol. 81 : p. 066102. 2010 Year 2010 Type Journal Type of publication ONCE-CS

## Optional Infos

 Abstract We analyze and exploit some scaling properties of the Affinity Propagation (AP) clustering algorithm proposed by Frey and Dueck (2007). First we observe that a divide and conquer strategy, used on a large data set hierarchically reduces the complexity ${\cal O}(N2)$ to ${\cal O}(N{(h+2)/(h+1)})$, for a data-set of size N and a depth h of the hierarchical strategy. For a data-set embedded in a d-dimensional space, we show that this is obtained without notably damaging the precision except in dimension d=2. In fact, for d>2 the relative loss in precision scales like $N{(2-d)/(h+1)d}$. Finally, under some conditions we observe that there is a value $s*$ of the penalty coefficient, a free parameter used to fix the number of clusters, which separates a fragmentation phase (for ss*) of the underlying hidden cluster structure. At this precise point holds a self-similarity property which can be exploited by the hierarchical strategy to actually locate its position. From this observation, a strategy based on AP can be defined to find out how many clusters are present in a given dataset. Bibtex @ARTICLE{FURTLEHNER:2010:INRIA-00420407:2, author = {Furtlehner, C. and Sebag, M. and Xiangliang, Z.}, title = {{S}caling {A}nalysis of {A}ffinity {P}ropagation}, year = {2010}, volume = {81}, pages = {066102}, note = {14 pages, 11 figures}, journal = {{P}hysical {R}eview {E}: {S}tatistical, {N}onlinear, and {S}oft {M}atter {P}hysics}, url = {http://hal.inria.fr/inria-00420407/en/}, affiliation = {{TAO} - {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {CNRS} : {UMR}8623 - {U}niversit{\'e} {P}aris {S}ud - {P}aris {XI}}, audience = {internationale}, language = {{A}nglais}, hal_id = {inria-00420407}, keywords = {{C}lustering; {B}elief-{P}ropagation; {E}xtrem value statistics; {S}cale invariance; {R}enormalization}, doi = {10.1103/PhysRevE.81.066102}, } Created Tuesday 10 May, 2011 12:56:22