Affinity propagation for Gelly

[Yi ZHOU]

Hello everyone,

I am working on  affinity propagation implementation for Gelly (FLINK 
1707 <https://issues.apache.org/jira/browse/FLINK-1707>).    The 
algorithm passes messages between every pair of vertices (NOT every pair 
of connected vertices) in each iteration with computation complexity 
(N²*Iter), it has a memory complexity of O(N²) also. So I believe  the 
algorithm will suffer from large communication complexity, no matter how 
we distribute the graph into different machines. The simple fact is that 
the algorithm passing two kinds of message on a complement graph. I see 
some similar discussion in SPARK 
<https://issues.apache.org/jira/browse/SPARK-5832>

I found an adaptive implementation on hadoop, It runs affinity 
appropagation on the  subgraphs , then merges  these clusters into 
larger ones. 
http://www.ijeee.net/uploadfile/2014/0807/20140807114023665.pdf . It is 
not equal to the original algorithm. So,does any one know another 
distributed version or have any suggestions?


ZHOU Yi