In this chapter, we report a comprehensive evaluation of the topological structure of protein-protein interaction (PPI) networks, by mining and analyzing graphs constructed from the popular data sets publicly available to the bioinformatics research community. We compare the topology of these networks across different species, different confidence levels, and different experimental systems used to obtain the interaction data. Our results confirm the well-accepted claim that the degree distribution follows a power law. However, further statistical analysis shows that residues are not independent on the fit values, indicating that the power law model may be inadequate. Our results also show that the dependence of the average clustering coefficient on the vertices degree is far from a power law, contradicting many published results. For the first time, we report that the average vertex density exhibits a strong powder law dependence on the vertices degree for the networks studied, regardless of species, confidence levels, and experimental systems. We also present an efficient and accurate approach to detecting a community in a protein-protein interaction network from a given seed protein. Our experimental results show strong structural and functional relationships among member proteins within each of the communities identified by our approach, as verified by MIPS complex catalog database and annotations.