TLocClust Class Reference

List of all members.

Public Member Functions
	TLocClust (const PUNGraph &GraphPt, const double &AlphaVal)
int	Len () const
	Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score.
int	GetRndWalkSup () const
	Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score.
int	GetNId (const int &NodeN) const
	Returns the ID of the NodeN-th node in the sweep vector.
int	GetVol (const int &Nodes) const
	Returns the volume of the set of first NodeN nodes in the sweep vector.
int	GetCut (const int &Nodes) const
	Returns the size of the cut of the first Nodes nodes in the sweep vector.
double	GetPhi (const int &ValId) const
	Returns the conductance of the cut separating the first Nodes nodes in the sweep vector from the rest of the graph.
int	BestCut () const
	Index K of the cut of the minimum conductance around the seed node.
int	BestCutNodes () const
	Number of nodes inside the 'best' (minimum conductance) cut.
int	GetCutEdges () const
	Number of edges in the 'best' (minimum conductance) cut.
int	GetCutVol () const
	Volume of the 'best' (minimum conductance) cut.
double	GetCutPhi () const
	Conductance of the 'best' (minimum conductance) cut.
int	ApproxPageRank (const int &SeedNode, const double &Eps)
	Computes Approximate PageRank from the seed node SeedNId and with tolerance Eps.
void	SupportSweep ()
	After the function ApproxPageRank() has been run the SupportSweep() computes the volume, cut size, node ids, conductance vectors.
void	FindBestCut (const int &SeedNode, const int &ClustSz, const double &MinSizeFrac=0.2)
	Finds minimum conductance cut in the graph around the seed node.
void	PlotVolDistr (const TStr &OutFNm, TStr Desc=TStr()) const
	Plots the cluster volume vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
void	PlotCutDistr (const TStr &OutFNm, TStr Desc=TStr()) const
	Plots the cluster cut size vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
void	PlotPhiDistr (const TStr &OutFNm, TStr Desc=TStr()) const
	Plots the cluster conductance vs. cluster size K (cluster is composed of nodes NIdV[1...K]).
void	SavePajek (const TStr &OutFNm) const
	Saves the network in the Pajek format so it can be visualized. Red node represents the seed and color the cluster membership.
Static Public Member Functions
static void	DrawWhiskers (const PUNGraph &Graph, TStr FNmPref, const int &PlotN)
	Draws the 'whiskers' of the graph. Whiskers are small sub-graphs that are attached to the rest of the graph via a single edge.
static void	GetCutStat (const PUNGraph &Graph, const TIntV &NIdV, int &Vol, int &Cut, double &Phi, int GraphEdges=-1)
	For a given Graph and a set of nodes NIdV the function returns the Volume, CutSize and the Conductance of the cut.
static void	GetCutStat (const PUNGraph &Graph, const TIntSet &NIdSet, int &Vol, int &Cut, double &Phi, int GraphEdges=-1)
	For a given Graph and a set of nodes NIdV the function returns the Volume, CutSize and the Conductance of the cut.
static void	PlotNCP (const PUNGraph &Graph, const TStr &FNm, const TStr Desc="", const bool &BagOfWhiskers=true, const bool &RewireNet=false, const int &KMin=10, const int &KMax=Mega(100), const int &Coverage=10, const bool &SaveTxtStat=false, const bool &PlotBoltzman=false)
Static Public Attributes
static bool	Verbose = true
Friends
class	TLocClustStat

---

Detailed Description

Local Spectral Clustering algorithm. The code implements the PageRank Nibble local clustering algorithm of Andersen, Chung and Lang. Given a single starting seed node, the algorithm will then find the clusters around that node. This is achieved by the algorithm finding the approximate personalized PageRank score of every node with respect to the Seed node. Nodes are then ordered by the PageRank score and the idea is then that by 'sweeping' the vector of PageRank scores one can find communities around the chosen seed node. The idea is to try out K = 1...N/2 and then for a set of {node_1 ... node_K} test the value of the conductance (Phi). If the conductance at certain value of K achieves a local minima, then we found a good cut in the graph. This method is also used for computing the Network Community Profile plots. See: Local Graph Partitioning using PageRank Vectors by R. Andersen, F. Chung and K. Lang URL: http://www.math.ucsd.edu/~fan/wp/localpartition.pdf

---

Constructor & Destructor Documentation

TLocClust::TLocClust	(	const PUNGraph &	GraphPt,
		const double &	AlphaVal
	)		[inline]

---

Member Function Documentation

int TLocClust::ApproxPageRank	(	const int &	SeedNode,
		const double &	Eps
	)

Computes Approximate PageRank from the seed node SeedNId and with tolerance Eps.

The algorithm basically sets the PageRank scores of nodes with score <Eps to zero. So the lower the value of Eps the longer the algorithm will run.

int TLocClust::BestCut

(

)

const [inline]

Index K of the cut of the minimum conductance around the seed node.

This means that the set of GetNId(0)...GetNId(K) forms the best cut around the seed node.

int TLocClust::BestCutNodes

(

)

const [inline]

Number of nodes inside the 'best' (minimum conductance) cut.

void TLocClust::DrawWhiskers	(	const PUNGraph &	Graph,
		TStr	FNmPref,
		const int &	PlotN = 10
	)		[static]

Draws the 'whiskers' of the graph. Whiskers are small sub-graphs that are attached to the rest of the graph via a single edge.

void TLocClust::FindBestCut	(	const int &	SeedNode,
		const int &	ClustSz,
		const double &	MinSizeFrac = 0.2
	)

Finds minimum conductance cut in the graph around the seed node.

Function first computes the ApproxPageRank(), initializes the SupportSweep() and then find the minimum conductance cluster. Parameter ClustSz controls the expected cluster size and is used to determine the tolerance (Eps) of the approximate PageRank calculation.

int TLocClust::GetCut

(

const int &

Nodes

)

const [inline]

Returns the size of the cut of the first Nodes nodes in the sweep vector.

Size of the cut is the number of edges pointing between the first Nodes nodes and the remainder of the graph.

int TLocClust::GetCutEdges

(

)

const [inline]

Number of edges in the 'best' (minimum conductance) cut.

double TLocClust::GetCutPhi

(

)

const [inline]

Conductance of the 'best' (minimum conductance) cut.

void TLocClust::GetCutStat	(	const PUNGraph &	Graph,
		const TIntV &	NIdV,
		int &	Vol,
		int &	Cut,
		double &	Phi,
		int	GraphEdges = -1
	)		[static]

For a given Graph and a set of nodes NIdV the function returns the Volume, CutSize and the Conductance of the cut.

void TLocClust::GetCutStat	(	const PUNGraph &	Graph,
		const TIntSet &	NIdSet,
		int &	Vol,
		int &	Cut,
		double &	Phi,
		int	GraphEdges = -1
	)		[static]

For a given Graph and a set of nodes NIdV the function returns the Volume, CutSize and the Conductance of the cut.

int TLocClust::GetCutVol

(

)

const [inline]

Volume of the 'best' (minimum conductance) cut.

int TLocClust::GetNId

(

const int &

NodeN

)

const [inline]

Returns the ID of the NodeN-th node in the sweep vector.

double TLocClust::GetPhi

(

const int &

ValId

)

const [inline]

Returns the conductance of the cut separating the first Nodes nodes in the sweep vector from the rest of the graph.

Conductance is the ration Cut/Volume. The lower the conductance the 'better' the cluster (higher volume, less edges cut).

int TLocClust::GetRndWalkSup

(

)

const [inline]

Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score.

int TLocClust::GetVol

(

const int &

Nodes

)

const [inline]

Returns the volume of the set of first NodeN nodes in the sweep vector.

Volume is defined as the sum of the degrees of the first Nodes nodes. Or in other words volume = 2* edges inside the set + the edges pointing outside the set.

int TLocClust::Len

(

)

const [inline]

Returns the support of the approximate random walk, the number of nodes with non-zero PageRank score.

void TLocClust::PlotCutDistr	(	const TStr &	OutFNm,
		TStr	Desc = TStr()
	)		const

Plots the cluster cut size vs. cluster size K (cluster is composed of nodes NIdV[1...K]).

void TLocClust::PlotNCP	(	const PUNGraph &	Graph,
		const TStr &	FNm,
		const TStr	Desc = "",
		const bool &	BagOfWhiskers = true,
		const bool &	RewireNet = false,
		const int &	KMin = 10,
		const int &	KMax = Mega(100),
		const int &	Coverage = 10,
		const bool &	SaveTxtStat = false,
		const bool &	PlotBoltzman = false
	)		[static]

Plots the Network Community Profile (NCP) of a given graph Graph. The NCP plot of a network captures the global community structure of the network. The NCP plot of a network captures the global community structure of the network. Refer to 'Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters by J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Internet Mathematics 6(1) 29--123, 2009' for the explanation of how to read these plots. URL: http://arxiv.org/abs/0810.1355

void TLocClust::PlotPhiDistr	(	const TStr &	OutFNm,
		TStr	Desc = TStr()
	)		const

Plots the cluster conductance vs. cluster size K (cluster is composed of nodes NIdV[1...K]).

void TLocClust::PlotVolDistr	(	const TStr &	OutFNm,
		TStr	Desc = TStr()
	)		const

Plots the cluster volume vs. cluster size K (cluster is composed of nodes NIdV[1...K]).

void TLocClust::SavePajek

(

const TStr &

OutFNm

)

const

Saves the network in the Pajek format so it can be visualized. Red node represents the seed and color the cluster membership.

void TLocClust::SupportSweep

(

)

After the function ApproxPageRank() has been run the SupportSweep() computes the volume, cut size, node ids, conductance vectors.

---

Friends And Related Function Documentation

friend class TLocClustStat [friend]

---

Member Data Documentation

bool TLocClust::Verbose = true [static]

---

The documentation for this class was generated from the following files:

• snap-adv/ncp.h
• snap-adv/ncp.cpp