I think I understand the praenomen, nomen, and cognomen for Roman aristocrats. What puzzles me is the additional cognonem or agnomen.
For example, in 312 Flavius Valerius Aurelius Constantinus fought Marcus Aurelius Valerius Maxentius.
So are the Constantinus and the Maxentius both agnomen? Was it common that late in the game for the aristocracy to have these honorifics or was it just that these two happened to be exceptions since both were co-emperors at the time? If it was common, when did it become common?
And while I know that Roman names were reused frequently, how meaningful is it that Valerius Aurelius fought Aurelius Valerius?
I think what you’re looking at is called an agnomen, a second cognomen. It was used to identify a sub-family within a family. And, of course, if a person was adopted still more names might be added.
I think this sort of thing was common. The pre-imperial name of the Emperor we know Antoninus Pius was T. Aurelius Fulvus Boionius Arrius Antoninus. At least part of this name defines his sub-family within the larger family unit.
Sometimes Romans took on additional names to honor another person, or to make a personal statement about themselves. (To me it seems that they “thought” about the concept of names quite differently than we do.)
The African-born Roman Emperor Septimius Severus (r.193-211) had the proper three-part Roman name of L. Septimius Severus. After the murder of the Emperor Pertinax (who had followed Marcus Aurelius’s son Commodus as Emperor) in March 193, Septimius Severus proclaimed himself L. Septimius Severus Pertinax Augustus, thereby styling himself Pertinax’s avenger in his bid to be Emperor.
Later, he inserted “Pius” into his name, by way of stating his continued deference to Pertinax’s memory: L. Septimius Severus Pius Pertinax.
Mississipienne has a point about adoption, too. At least through the 2nd century CE, Roman Emperors often adopted their (designated) heirs, and the names of the adopted sons were added to, or changed, apparently to reflect that adopted ancestry and strengthen the connection to it.
Speaking of names, Mississippienne, how many double-letters can one name have? 
Rome had a thousand year history, and customs changed greatly over that millennium. Just saying “this sort of thing was common” isn’t specific enough, I’m afraid. Was it common all the time or only after a certain point? When were subfamily names used? Is some of this due to modern conventions about referring to Romans rather than the full names they used at the time?