1.1 Friends-of-Friends Masses

1.1.1 Friends-of-Friends Mass for an N-Body Simulation

Notation: cue_mathinline.gif

(The number cue_mathinline.gif

is the linking length used to determine the friends of a particle in units of the mean interparticle separation.)

Introduction: Friends-of-friends (FOF) is an algorithm that aims to identify overdense objects in observed galaxy distributions as well as in cosmological simulations of dark matter. Early descriptions can be found in Huchra and Geller (1982), who identified galaxy groups in redshift space, and Press and Davis (1982), who employed "an efficient algorithm given by Knuth (1968)" to both observed and simulated galaxy catalogs and who coined the algorithm's name by describing pairs as "friends" along with the rule "any friend of a friend is a friend". The algorithm selects members (particles or galaxies, the former is used hereafter) that roughly lie within a local iso-density contour that is determined by a free parameter called the linking length. Denoted by the symbolcue_mathinline.gif

the linking length is usually quoted in units of the mean inter-particle separationcue_mathinline.gif

where cue_mathinline.gif

denotes the average number density of particles. The local isodensity contour (roughly) selected by the FOF algorithm is given by cue_mathinline.gif

where the numbercue_mathinline.gif

is a dimensionless number that comes from continuum percolation theory (see More et al. 2011). For the commonly used value ofcue_mathinline.gif

this corresponds to a local density that is 81.62 times the mean background density. As noted in the discussion below, the value of this local density, along with the mean density enclosed within the isodensity contour, depends on the degree of resolution (mean particle density) as well as the internal structure of a group.

Algorithmic Description: Here we describe the algorithm that is commonly used with dark matter simulations. The FOF algorithm has a single free parameter called the linking length. Any two dark matter particles that are separated by a distance less than or equal to the linking length are called "friends". The FOF group is then defined by the set of particles for which each particle within the set is connected to every other particle in the set through a network of friends. The following procedure can be used to identify FOF halos in cosmological simulations of dark matter structure.
  1. Set FOF group counter j=1.
  2. For each particle, n, not yet associated with any group:
    • Assign n to group j, initialize a new member list, mlist, for group j with particle n as first entry,
    • Recursively, for each new particle p in mlist:
      • Find neighbors of p lying within a distance less than or equal to the linking length, add to mlist those not already assigned to group j,
    • Record mlist for group j, set j=j+1.

At the end of this algorithm, all the dark matter particles will belong to at least one group. (Groups with members less than a minimum number of particles are often ignored.) The above algorithm is intended to be illustrative; other methods exist to achieve the same end result.

Links to Software:
  • FOF halo finders:
    • The N-Body Shop from the University of Washington has a FOF code that can accept input in a TIPSY format. Email Surhud More if you have data in the ART format and want to run the N-Body Shop code.
    • The yt set of python tools also has a parallel FOF halo finder which can accept data from ENZO simulations.
    • Rockstar is a parallel group-finding algorithm, developed by Peter Behroozi and collaborators at Stanford, that starts with a FOF tessellation, then recursively subdivides the FOF halos using their 6D phase-space structure.
    • Volker Springel has a parallel implementation of the FOF code which can be obtained (webpage says collaborators only) by sending him an email.
  • Software to calculate the overdensity as a function of halo mass selected by the FOF is located here

  • Simplicity. The method (in real space) is controlled by a single parameter. There is no need to choose a group center.
  • Uniqueness. Each particle is assigned to one and only one group, and membership should be independent of specific algorithmic implementation (round-off error in the pairwise distance calculation is the only potential source of confusion).
  • Geometrically neutral. The outer isodensity contour traces the aspherical shape of a dark matter halo.
  • Recursive nature of the group hierarchy. All members of a certain group identified with linking lengthcue_mathinline.gif

    will also be common members of another group found with linking lengthcue_mathinline.gif

  • Relatively easy to parallelize.

  • Not observer friendly. Except for application to redshift space galaxy overdensities, the group properties (e.g., mass, membership) are difficult to relate to observables of groups and clusters.
  • Dynamically agnostic. Being based only on position information, particles in a FOF group are not guaranteed to be self-bound.
  • Bridging. Large linking lengths can percolate across filaments and join dynamically distinct halos.
  • Lack of center. The algorithm does not require a center to be defined. The center of mass, most bound particle or highest density particle are frequently used to define centers, and these positions can differ substantially depending on the linking used and the dynamical state of the halo.
  • Resolution dependence. The fuzziness of the halo boundary, hence the halo mass, depends upon the numerical resolution.

The FOF algorithm's strengths, particularly its simplicity, geometric neutrality and its connections to percolation and network theory, imply that this method is likely to remain viable. However, the difficulty in relating FOF masses to observationally relevant quantities poses a limitation to its practical use in cluster cosmology studies.

As the algorithm selects all particles within an iso-density contour, the volume-averaged overdensity of the selected structure is dependent on the density profile of the halo. In case of the Navarro, Frenk & White (1997) (NFW) density profile, halo concentration depends on mass and redshift in a cosmology-dependent manner. At fixed halo mass, the scatter in concentrations causes the FOF halos to have a considerable range of average overdensities. Forcue_mathinline.gif

the overdensity ranges from 250 at high masses to 500 at low masses. The exact expression for the dependence of overdensity and an algorithm to calculate it can also be found in More et al. (2011).

In the same paper, the authors also show that when FOF is run on spherically symmetric mock NFW haloes which have the same concentration but with varying number of particles (i.e., mass resolution), the mass selected by the algorithm changes. The mass of the mock halo selected by the FOF algorithm gradually declines as the numerical resolution is increased. This effect was first reported by Warren et al. (2006)and later by Lukic et al. (2009). Warren et al. (2006) found a phenomenological formula to correct for this effect and this is very commonly used in the literature. Lukic et al (2009) demonstrated that this formula should also have a concentration dependence. This behavior can be understood in terms of percolation theory. The dimensionless percolation threshold cue_mathinline.gif

is expected to be smaller when the numerical resolution is low and in a manner which is predicted by percolation theory. A correction formula motivated by percolation theory is also presented in More et al. (2011). This formula is also able to explain the results of the resolution studies carried out by Warren et al. (2006) and Lukic et al. (2009). It also works perfectly well for halos with a smooth density distribution even in the case of haloes that have triaxiality similar to that found in real dark matter haloes.

However, More et al. (2011)show that in the presence of substructure, the formula motivated by percolation theory overcorrects for the resolution dependence. The effect is large enough to make percent-level precision determination of the halo mass function difficult. It was found that at low resolution, FOF has the tendency not to link the substructure in outer parts of the haloes and this counteracts the tendency of FOF to percolate to a lower density threshold and select a larger mass. As the amount of substructure in the outer parts of haloes is most likely redshift and cosmology dependent, it would not be correct to use the correction for real halos in simulations. The same applies to the correction formulae presented by Warren et al. (2006) and Lukic et al. (2009).

[Add links to early works on FOF vs. SO? e.g., Lacey and Cole `94, M. White `02, others?]

Principal author(s): Surhud More, Gus Evrard
Contributing author(s): ??