Motivated by the idea that some characteristics are specific of the relations between individuals and not of the individuals themselves, we model them as states on the links in a network of interacting agents. Each link in the network can be in one of two equivalent states and, in each dynamical step a link is chosen, and this one takes the state of the majority of links surrounding it. We can characterize the nodes by the link heterogeneity index, which measures the tendency of a node to have links in one state or the other. On a fully connected network and a square lattice we fully characterize the non-trivial asymptotic configurations accessible from random initial conditions. For Erdös-Renyi random networks we also characterize the asymptotic configurations and the mechanisms leading to them. All these non-trivial asymptotic configurations are quite heterogeneous for a fully connected network and random networks. Furthermore those configurations are not stable for the node majority rule, which highlights the importance of modeling link-based dynamics. Once the asymptotic states are understood we can explain the evolution of the distributions of link heterogeneity indices on the different networks.