The thing is that, when I speak about Arabs, I mean Qahtan Arabs( for lack of a better word, true Arabs), most people from North Africa, Palestine, Kuwait, North Arabia outside of the Levantine were not considered Arabs in ancient times.
Medieval Arab genealogists divided Arabs into three groups:
1) "Ancient Arabs", tribes that had vanished or been destroyed, such as ʿĀd and Thamud, often mentioned in the Qur'an as examples of God's power to destroy those who did not believe and follow their prophets and messengers.
All contemporary Arabs were considered as descended from the later two, groups with the ancestors, Qahtan and Adnan.
2)
Qahtan "Pure Arabs" of South Arabia, descending from Qahtan.
The Qahtanites (Qahtanis) are said to have migrated from the land of Yemen following the destruction of the Ma'rib Dam (sadd Ma'rib). Semitic peoples either originating in, or claiming genealogical descent from the southern extent of the Arabian Peninsula, especially from Yemen
3)
Adnanite
The "Arabized Arabs" (musta`ribah) of center and North Arabia, descending from Ishmael the elder son of Abraham. Adnan is the traditional ancestor of the Adnanite Arabs of Northern, Western and Central-Western Arabia,According to tradition, Adnan is the father of a group of the Ishmaelite Arabs who inhabited West and Northern Arabia. Adnan is believed by Arab genealogies to be the father of many Ishmaelite tribes along the Western coast of Arabia, Northern Arabia and Iraq .
When I speak about Arabs in ancient times, the Qahtan Arabs are the group Im referring to. Anybody can be Arab if their forefather(which is why sudanese people, and alot north African people consider themselves Arab, by that definition Im Arab and I look like Chris Brown
), or they are native speaker of Arabic.
Having said that there is multitude of sources that show the connections of Arabia and Africa;
-Linguistics(Afro-Asiatic)
-Axum and Sabeans
-Al-Jahiz
-Others, just do some damn research its alot on the net.