<p>First of all, let me mention that I think METIS is the wrong tool here, because it is used for <strong>graph partitioning</strong>, where the emphasis is on <em>minimizing the number of edges between partitions</em> while <em>keeping the partitions balanced</em> (more or less equal sizes)</p>

<p>What you probably want to do is <strong>community detection</strong> within social networks, i.e. the search for clusters which <em>maximize internal connectivity</em> (large number of edges between nodes from the same cluster) and <em>minimize external connectivity</em> (small number of edges between different clusters).<br>
This can be achieved by maximizing the so-called <a href="https://en.wikipedia.org/wiki/Modularity_(networks)" rel="nofollow noreferrer">Modularity</a> of the clustering</p>

<p>There are several approaches to tackle this problem, a popular heuristic being <a href="https://arxiv.org/abs/0709.2938" rel="nofollow noreferrer">Label propagation</a>.<br>
If you don't want to implement the algorithm yourself, I would recommend using a framework like <a href="https://networkit.iti.kit.edu/" rel="nofollow noreferrer">NetworKit</a> (unfortunately, I don't know any other such frameworks yet), which implements <a href="https://networkit.iti.kit.edu/api/doxyhtml/class_networ_kit_1_1_l_p_degree_ordered.html" rel="nofollow noreferrer">Label propagation</a>, some <a href="https://networkit.iti.kit.edu/api/doxyhtml/class_networ_kit_1_1_parallel_agglomerative_clusterer.html" rel="nofollow noreferrer">modularity-based algorithms</a> and many helpful tools.</p>

<p>But back to your original question:</p>

<p><strong>What is <code>-ptype=rb/kway</code>?</strong></p>

<p>There are multiple ways how you can approach the graph partitioning problem: You can either try to partition the graph into your desired number of partitions directly (k-way partitioning) or you can split the graph in half repeatedly until you have the desired number of partitions (recursive bisection, rb)</p>

<p><strong>What is the jth constraint?</strong></p>

<p>METIS allows you to try and optimize multiple balance constraints at the same time, i.e. if you have multiple types of calculations on the graph that should all be more or less balanced among the compute nodes.</p>

<p>See the manual:</p>

<blockquote>
  <p>Many important types of multi-phase and multi-
  physics computations require that multiple quantities be load balanced simultaneously.
  [...]<br>
  METIS includes partitioning routines that can be used to partition a graph in the presence of such multiple balancing
  constraints. Each vertex is now assigned a vector of m weights and the objective of the partitioning routines is
  to minimize the edge-cut subject to the constraints that each one of the m weights is equally distributed among the
  domains.</p>
</blockquote>

<p>EDIT: Since you clarified that you wanted to look at a <strong>fixed number of clusters</strong>, I see how graph partitioning could be helpful here. Let me illustrate what <code>ufactor</code> means:</p>

<p>The <em>imbalance</em> of a partitioned graph is (in this simple case) computed as the maximum of the imbalance for each partition, which is roughly the quotient <code>partition size / average partition size</code>. So if we allow a maximum imbalance of 2, this means that the largest partition is twice as big as the average partition. Note however that <code>ufactor</code> doesn't specify the imbalance directly, it specifies how many permille away from 1 the imbalance is allowed to be.
So <code>ufactor=143</code> actually means that your maximal allowed imbalance is 1.143, which makes sense since your clusters are not that far from each other. So in your case, you will probably use larger values for ufactor to allow the groups to be of quite different sizes.</p>

<p><strong>Consequences of large imbalance</strong></p>

<p>If your imbalance is too large, it might happen that all the strongly-connected parts land in the same partition while only isolated nodes are put in the other partitions. This is due to the fact that the algorithm tries to minimize the number of <em>cut edges</em> between different partitions, which will be lower if we put all the high-degree nodes in the same partition.</p>

<p><strong>What about spectral partitioning, ...?</strong></p>

<p>The general approach of METIS works as follows:<br>
Most input graphs are too large to partition directly, which is why so-called multilevel methods are used:</p>

<ul>
<li>The graph is first <em>coarsened</em> (nodes are combined while trying to preserve the graph structure) until its size becomes feasible to partition directly</li>
<li>The coarsest graph is partitioned using an <em>initial partitioning</em> technique, where we could use a variety of approaches (combinatorial bisection, spectral bisection, exact solutions using ILPs, ...).</li>
<li>The graph is then <em>uncoarsened</em>, where in each step a small number of nodes are moved from partition to partition in a <em>local search</em> to improve the overall edge cut.</li>
</ul>

<p><strong>My personal recommendation</strong></p>

<p>I should however note that while graph partitioning might be a valid model for your case, METIS itself might not be the ideal implementation for you:</p>

<p>As you can read on the METIS homepage, it is mostly used for rather sparse graphs ('finite element methods, linear programming, VLSI, and transportation'), whereas social networks are much denser and have a different structure (degrees follow a power-law distribution)</p>

<p>The coarsening approach of METIS uses <em>heavy edge matching</em> to combine nodes which are somehow close together, which works great for the intended applications, for social networks however, <em>clustering-based coarsening</em> techniques might prove more efficient.<br>
Another library that is a bit slower in general, but implements some presets especially for social networks is <a href="http://algo2.iti.kit.edu/kahip/" rel="nofollow noreferrer">KaHIP</a>, see the <a href="http://algo2.iti.kit.edu/schulz/software_releases/kahipv2.00.pdf" rel="nofollow noreferrer">manual</a> for details.</p>

<p>(I should mention however that I am biased in this regard, since I worked extensively with this library ;-) )</p>
'ufactor' parameter in metis for imbalance clustering
<p>I have been using <code>METIS</code> for clustering social media users.</p>

<p>By default, it was outputting clusters with same number of vertices in each side, which is not ideal in real world scenario. So, I was trying to find way to loosen the constraint of "same number of vertices" and get possible imbalance partition with minimized cut value.</p>

<p>I find a parameter <code>ufactor</code> in the manual which is suitable(I think) for my case but I did not grasp what it is really doing. I have large graph and tried with some value of <code>ufactor</code>. For one data set <code>ufactor=1000</code> works very well but for another dataset it could not even partition the graph. I can not interpret this result as i did not understand what it's really doing. Here is what i find in the manual about this:</p>

<blockquote>
  <p>Specifies the maximum allowed load imbalance among the partitions. A value of x indicates that the
      allowed load imbalance is (1 + x)/1000. The load imbalance for the jth constraint is defined to be
      max_i(w[j, i])/t[j, i]), where w[j, i] is the fraction of the overall weight of the jth constraint that 
      is assigned to the ith partition and t[j, i] is the desired target weight of the jth constraint for the 
      ith partition (i.e., that specified via -tpwgts). For -ptype=rb, the default value is 1 (i.e., load 
      imbalance of 1.001) and for -ptype=kway, the default value is 30 (i.e., load imbalance of 1.03).</p>
</blockquote>

<p>Can anybody help me to interpret this? Here, what is <code>jth</code> constraints? what is <code>-ptype=rb/kway</code>?</p>