Describing the connectivity of chemical and/or biological systems using networks is a straight gate for the introduction of mathematical tools in proteomics. Networks, in some cases even very large ones, are simple objects that are composed at least by nodes and edges. The nodes represent the parts of the system and the edges geometric and/or functional relationships between parts. In proteomics, amino acids, proteins, electrophoresis spots, polypeptidic fragments, or more complex objects can play the role of nodes. All of these networks can be numerically described using the so-called Connectivity Indices (CIs). The transformation of graphs (a picture) into CIs (numbers) facilitates the manipulation of information and the search for structure-function relationships in Proteomics. In this work, we review and comment on the challenges and new trends in the definition and applications of CIs in Proteomics. Emphasis is placed on 1-D-CIs for DNA and protein sequences, 2-D-CIs for RNA secondary structures, 3-D-topographic indices (TPGIs) for protein function annotation without alignment, 2-D-CIs and 3-D-TPGIs for the study of drug-protein or drug-RNA quantitative structure-binding relationships, and pseudo 3-D-CIs for protein surface molecular recognition. We also focus on CIs to describe Protein Interaction Networks or RNA co-expression networks. 2-D-CIs for patient blood proteome 2-DE maps or mass spectra are also covered.