Packages

class Partition[TLabel] extends AnyRef

The Partition class is used to partition large directed graphs. It support the following three algorithms: 'group_ran', 'group_ord', 'group_lp'.

(1) Random Partitioning - excellent balance, poor edge cuts Each vertex is given a randomly assigned integer label 'ilabel' and is grouped accordingly.

(2) Ordered Partitioning - excellence balance, edge cuts may or may not be good Each vertex is assigned an integer label 'ilabel' incrementally and is grouped accordingly, e.g., {0, 1, ..., 9}, {10, 11, ..., 19}, ...

(3) Label Propagation partitioning - fair balance, fair edge cuts Each vertex is initially given a unique integer label 'ilabel'. On each iteration, each vertex will have its 'ilabel' reassigned to the most popular/frequent 'ilabel' in its neighborhood (which includes its children, parents and itself).

See also

research.microsoft.com/pubs/183714/Partition.pdf ----------------------------------------------------------------------------

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. Partition
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new Partition(g: Graph[TLabel])(implicit arg0: ClassTag[TLabel])

    g

    the directed graph to partition

Value Members

  1. def formGraphs(): ArrayBuffer[Graph[TLabel]]

    Form subgraphs 'gi's from the original graph 'g'

  2. def group_lp(k: Int): Unit

    Group the vertices based on their 'ilabel's using label propagation.

    Group the vertices based on their 'ilabel's using label propagation.

    k

    the number of subgraphs to create

  3. def group_ord(k: Int): Unit

    Group the vertices based on the order of their 'ilabel's, which are assigned incrementally.

    Group the vertices based on the order of their 'ilabel's, which are assigned incrementally.

    k

    the number of subgraphs to create

  4. def group_ran(k: Int): Unit

    Group the vertices based on their randomly generated 'ilabel's.

    Group the vertices based on their randomly generated 'ilabel's.

    k

    the number of subgraphs to create

  5. def partition(): Unit

    Partition vertices with the same 'ilabel' after grouping.