You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@hama.apache.org by "Edward J. Yoon (JIRA)" <ji...@apache.org> on 2012/06/20 12:18:44 UTC
[jira] [Created] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Edward J. Yoon created HAMA-594:
-----------------------------------
Summary: Implementation of a Semi-Clustering algorithm, described in Pregel paper.
Key: HAMA-594
URL: https://issues.apache.org/jira/browse/HAMA-594
Project: Hama
Issue Type: New Feature
Components: examples, graph
Reporter: Edward J. Yoon
{quote}
5.4 Semi-Clustering
Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
....
{quote}
This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13440052#comment-13440052 ]
Edward J. Yoon commented on HAMA-594:
-------------------------------------
Here's guide for you. Someone can implement this?
{code}
@Override
public void compute(Iterator<SCMessage> messages) throws IOException {
if (this.getSuperstepCount() == 0) {
// In superstep 0, V enters itself in that list as a semi-cluster of
// size 1 and score 1, and publishes itself to all of its neighbors.
}
// In subsequent supersteps, V circulates over the received semi-clusters
SCMessage clusters = null;
while ((clusters = messages.next()) != null) {
for (SemiCluster c : clusters.getClusters()) {
// If a semi-cluster c does not already contain V, V is added to c to
// form c’.
}
}
// The semi-clusters are sorted by their scores and the
// best ones are sent to V’s neighbors.
// Vertex V updates its list of semi-clusters with the
// semi-clusters that contain V.
boolean updated = updateLocalClusters(clusters);
if (!updated) {
// The algorithm terminates either when the semi-
// clusters stop changing or the user may provide a
// limit.
// At that point, the list of best semi-cluster
// candidates for each vertex may be aggregated
// into a global list of best semi-clusters.
voteToHalt();
} else {
// The semi-clusters are sorted by their scores and the best ones are
// sent to V’s neighbors.
}
}
}
{code}
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13404392#comment-13404392 ]
Edward J. Yoon commented on HAMA-594:
-------------------------------------
See Hierarchical clustering, and http://people.apache.org/~edwardyoon/documents/pregel.pdf (67~ 73 pages).
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Thomas Jungblut (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13397540#comment-13397540 ]
Thomas Jungblut commented on HAMA-594:
--------------------------------------
http://people.apache.org/~tjungblut/downloads/pregel_paper.pdf
The algorithm seems to be quite cool.
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Zh h (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13404353#comment-13404353 ]
Zh h commented on HAMA-594:
---------------------------
execuse me, but i can't find the link to the inplementation code of the algorithm on this page.
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Tommaso Teofili (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13397549#comment-13397549 ]
Tommaso Teofili commented on HAMA-594:
--------------------------------------
cool, thanks Thomas.
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HAMA-594) Implementation of a Semi-Clustering
algorithm, described in Pregel paper.
Posted by "Tommaso Teofili (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HAMA-594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13397427#comment-13397427 ]
Tommaso Teofili commented on HAMA-594:
--------------------------------------
interesting, it'd be good to have a reference to the full paper
> Implementation of a Semi-Clustering algorithm, described in Pregel paper.
> -------------------------------------------------------------------------
>
> Key: HAMA-594
> URL: https://issues.apache.org/jira/browse/HAMA-594
> Project: Hama
> Issue Type: New Feature
> Components: examples, graph
> Reporter: Edward J. Yoon
>
> {quote}
> 5.4 Semi-Clustering
> Pregel has been used for several different versions of clus-tering. One version, semi-clustering, arises in social graphs. Vertices in a social graph typically represent people, and edges represent connections between them.
> ....
> {quote}
> This issue implements Semi-Clustering algorithm, described in Pregel paper, using Hama graph APIs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira