Gene expression is a dynamic process which can be controlled by a number of mechanisms as genetic information flows from nucleic acids to proteins. The study of gene expression in the steady state, while informative, overlooks the underlying dynamics of the processes. Steady-state transcript levels are a result of both RNA synthesis and degradation, and as such, measurements of degradation rates can be used to determine their rates of synthesis as well as reveal regulation that occurs via changes in RNA stability. Messenger RNA degradation plays a central role in diverse cellular processes and is controlled primarily by the activity of the degradosome in prokaryotes. In this study, we use the currently available network of protein-protein interactions (PPIs) and mRNA half-lives in Escherichia coli to demonstrate that centrality of a protein in the PPI network is strongly correlated with its mRNA half-life. We find that interacting proteins tend to show similar half-lives, commonly referred to as assortative behavior in networks, which is frequently found in biological and social networks. While a major fraction of the interacting proteins show significantly lower differences in mRNA stabilities, a smaller but significant number of protein pairs tend to show higher differences than expected by chance. Higher differences in transcript stabilities often involved those that encode for transcription factors and enzymes, suggesting a feedback link at the post-translational level. We also note that although essential genes, which act as a proxy for in vivo centrality in PPI networks, are highly expressed compared to non-essential ones, they do not encode for more stable transcripts than non-essential genes. Our results provide a direct link between mRNA stability and centrality of a protein in PPI network indicating the importance of post-transcriptional mechanisms on nascent RNAs in the cell.