Akalanka,

As far as I remember this data set was published in 2003 by D. Lusseau.

So why you don't ask directly David ([email protected])?

Best regards,

Jacek

Perhaps you are calculating sum of eigenvalues of individual nodes, no matter whatever is the case, eigenvalues has nothing to do with number of components in a graph, it tells you the importance of a node or a community (number of nodes), but certainly nothing about connected components. DFS/BFS are the procedures to find components, in this case you should rely on the results by DFS/BFS.

You can find the connected components, then count those.  As others have pointed out, you want to build on DFS or BFS.  You can find the algorithm for this in the following paper (while if you understand DFS or BFS, it's not complicated):

Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16 (6): 372–378

I can't really find the reference right now regarding eigenvalue based method. It uses the laplacian matrix and decomposed to eigenvalues and vectors. Then number of 0 in eigenvalue set is number of connected components. I was manually doing it and use the function available in network toolbox for Octave. In Gephi, its BFS/DFS. This brings me to the ambiguous situation. However I'll look into the references pointed by Daniel Page and asked from   Lusseau as pointed out by Jacek Czerniak.

Use Dijkstra's algorithm. Can be found in any text book on algorithms and data structures such as Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

As mentioned by others, running a BFS or DFS will allow you to efficiently count the number of connected components. The key here is that you don't stop the search when the frontier of the search can no longer be expanded. You need to start a new search from the remaining unvisited vertices. Each start of a new search adds 1 to your connected component count.

I can also confirm that the dolphin data set has 1 connected component.

graph search should give you a definite reseach.

Majid, I was using a similar function 'isConnected(A) | numConnComp(A)' where A is adjacency matrix in Octave/network toolbox. 

https://github.com/aeolianine/octave-networks-toolbox

Majid, yes both Matlab and Octave works pretty much similar way. In-fact network toolbox is for both software. I have already tried few simple networks and network with 20 nodes. For them, it returns as connected graphs. I assume the issue is with rounding up the eigenvalues (10E-16~0). When network is simple, eigenvalues doesn't go for such small values. Even for karate club it returns as connected. 

In the R environment you have the igraph package. There you have methods to compute the number of connected components. In the following paper you can see how this is used to measure the quality enhancement made to a knowledge graph: Conference Paper Repairing Hidden Links in Linked Data: Enhancing the quality...