What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the terms mean the same or are they different?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ The answer is probably similar to your other question. I suggest you look up how these terms are actually used in your context, for example by looking for relevant papers containing these terms. $\endgroup$– Yuval FilmusMar 20, 2016 at 17:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
They are different because... :
Graph Partitioning:
Giving a graph $G=(V,E)$, it is possible to partition $G$ into smaller components with specific properties.
e.g. the k-way graph partitioning is the problem to divide the vertex set $V$ into $k$ disjoint partition $P_1, P_2,...,P_k$ such that the number of the edges $e = (u,v) \in E, s.t. u \in P_i , v \in P_j, i \neq j $ is minimum.
Graph Coarsening:
Graph Coarsening is the first phase of a Multi-level Method, a method that partitions a graph applying one or more stage. Usually the first phase is the Graph Coarsening. This works by collapsing pairs of nodes and edges using a determinate criteria. Graph Coarsening takes as input a graph $G$ and gives as output a smaller graph $G^{'}$.
We use the Graph Coarsening because the size of the graphs may be too big to be partitioned using well known algorithms (i.e. FM, KL) in an acceptable time.
e.g. METIS uses multi-level methods and, in this Coarsening Phase, merges pairs of nodes having a matching.
In your analysis you can use Graph Partitioning Software (METIS, Chaco, etc) in order to divide you graph and (for example) put each partition on a different node and doing distributed computing.
-
1$\begingroup$ You've marked up most of your answer as quotation but you've not given any source for those quotations. Are they actually quotations? $\endgroup$ Dec 2, 2016 at 12:35
-
$\begingroup$ I revoved unused quotations. I derived these informations from many articles. $\endgroup$– dariodipDec 2, 2016 at 16:09