Many biological phenomena or social events critically depend on how information evolves in complex networks. However, a general theory to characterize information evolution is yet absent. Consequently, numerous unknowns remain about the mechanisms underlying information evolution. Among these unknowns, a fundamental problem, being a seeming paradox, lies in the coexistence of local randomness, manifested as the stochastic distortion of information content during individual-individual diffusion, and global regularity, illustrated by specific non-random patterns of information content on the network scale. Here, we attempt to formalize information evolution and explain the coexistence of randomness and regularity in complex networks. Applying network dynamics and information theory, we discover that a certain amount of information, determined by the selectivity of networks to the input information, frequently survives from random distortion. Other information will inevitably experience distortion or dissipation, whose speeds are shaped by the diversity of information selectivity in networks. The discovered laws exist irrespective of noise, but noise accounts for disturbing them. We further demonstrate the ubiquity of our discovered laws by analyzing the emergence of neural tuning properties in the primary visual and medial temporal cortices of animal brains and the emergence of extreme opinions in social networks.