Alien encounters rumors only increase alien encounters by 100%. Even with patrolling and going over sectors with an alien encounters rumor repededly, the chance of an alien encounter is very, very small.
The best way to find aliens are on high difficulties, patrolling over indepndent dead planets, with artifacts and a xeno vet, early in the game (less than 400AE).
Tactics, Wisdom, Speed, sails, and bodyguard officer increase chance of ships for patrol in general, meaning they'll help a lot to find aliens for dead planet patrol. Also, the later the date, the harder patrol is. So earlier in the game is better for patrol in any location, including over dead planets.
Looking for them or not, you'll eventually encounter an alien, especially on high difficulties.